Question

Prove the following statements using either direct or contrapositive proof. Let \(a \in Z, n \in \mathbb{N}\). If \(a\) has remainder \(r\) when divided by \(n\), then \(a \equiv r(\bmod n)\).

Short answer

The statements can be proven using both direct and contrapositive proofs. In a direct proof, write \(a = nq + r\) and rearrange to \(r = a - nq\), which can be read as \(r\) is congruent to \(a\) modulo \(n\). In a contrapositive proof, write the contrapositive statement and show that if \(a\) is not congruent to \(r\) modulo \(n\), then the remainder of \(a\) divided by \(n\) is not \(r\).

Step-by-step solution

Understand division and remainder

Recall the definition of division in number theory, that is when \(a\) is divided by \(n\) with remainder \(r\), we can express \(a\) as \(a = nq + r\) for some integer \(q\). The \(r\) is what we also call \(a \bmod n\).

Direct proof

Now prove the theorem using direct proof. Write the statement of division from Step 1 as \(a = nq + r\). If we rearrange this to isolate \(r\), we get \(r = a - nq\). This equation should be read as \(r\) is congruent to \(a\) modulo \(n\), written as \(r \equiv a (\bmod n)\). That proves the statement.

Contrapositive proof

To further solidify the proof, show it using contrapositive proof. First write the contrapositive statement of the original: 'If \(a\) is not congruent to \(r\) modulo \(n\), then \(a\) does not have remainder \(r\) when divided by \(n\)'. If \(a\) is not congruent to \(r\) modulo \(n\), we can write \(a \neq nq + r\) for any integer \(q\), which means when \(a\) is divided by \(n\), the remainder is not \(r\), proving the contrapositive statement.

Key concepts

Number Theory Basics

Number theory is a fascinating branch of mathematics, deeply rooted in the exploration of properties and behaviors of numbers, especially integers. A fundamental aspect of number theory is the division algorithm, which defines how any integer 'a' can be divided by another positive integer 'n' to give a unique quotient 'q' and a remainder 'r'.

This process is denoted by the equation a = nq + r, where 0 ≤ r < n. A familiar example to illustrate this would be dividing 10 (a) by 3 (n), which would give us a quotient of 3 (q) and a remainder of 1 (r), fitting into the equation as 10 = 3*3 + 1.

Understanding the relationship between the divisor, dividend, quotient, and remainder is crucial for delving into more complex concepts in number theory, such as modular arithmetic and the topic at hand – proving a divisibility condition using congruences.

Direct Proof Strategy

A direct proof is a logical argument that confirms a mathematical statement by showing that the premises inevitably lead to the conclusion. The approach is straightforward: assume that the given premises are true, and logically deduce the statement's truth from them. In the context of our exercise, to prove that 'a' is congruent to 'r' modulo 'n', we start by accepting the division premise: 'a' can be expressed as 'a = nq + r'.

By isolating 'r', we get 'r = a - nq'. This equation essentially means that the difference between 'a' and 'nq' is exactly 'r', which is the definition of congruence modulo 'n'. Put simply, 'a' and 'r' leave the same remainder when divided by 'n', which is exactly what 'a ≡ r (mod n)' asserts, thereby directly proving our statement.

Contrapositive Proof Explained

A contrapositive proof takes an indirect route to reach the same destination as a direct proof. The basic template is to prove 'if not B, then not A', which is logically equivalent to 'if A, then B'. For our exercise where we want to prove if 'a' has a remainder 'r' when divided by 'n', then 'a ≡ r (mod n)', we look at the contrapositive: if 'a' is not congruent to 'r' modulo 'n', then 'a' does not have 'r' as a remainder.

If 'a' does not satisfy 'a ≡ r (mod n)', we can equivalently say 'a' can not be expressed as 'nq + r' for any integer 'q'. This implies that the remainder upon division by 'n' is not 'r', since the definition of congruence is not met. Thus, by proving the contrapositive, we affirm the original statement in an indirectly satisfying manner.

Delving into Modular Arithmetic

Modular arithmetic, a system of arithmetic for integers, is what governs the concept of congruence that we have been exploring. Often referred to as 'clock arithmetic', it focuses on the remainder after division. The key operation in modular arithmetic is finding the modulus, written as 'a mod n', which is the remainder of 'a' after division by 'n'.

The statement 'a ≡ r (mod n)' effectively says that 'a' and 'r' are equivalent up to a multiple of 'n', which gives us a powerful way to handle equivalences and solve problems constrained to these modular conditions. In practice, we use modular arithmetic to simplify computations, solve congruences, and even in areas like cryptography where the modular properties of numbers provide robust foundations for secure communications.

The beauty of modular arithmetic lies in its simplicity and applicability which make it an indispensable tool in the world of number theory and beyond.