Question

Prove the following statements using either direct or contrapositive proof. Let \(a, b \in \mathbb{Z}\) and \(n \in \mathbb{N}\). If \(a \equiv b(\bmod n)\), then \(a^{2} \equiv a b(\bmod n)\).

Short answer

Since a and b are integers such that their difference is an integer multiple of n, we have proven that the difference between \( a^{2} \) and \( ab \) will also be a multiple of n. Thus, if \( a \equiv b(\bmod n) \), then \( a^{2} \equiv a b(\bmod n) \). This verifies the statement.

Step-by-step solution

Understand the Statement

The statement is implying that if \( a \equiv b(\bmod n) \), we need to prove that \( a^{2} \equiv a b(\bmod n) \). This means if \( a \) and \( b \) are integers such that their difference is a multiple of \( n \), then the difference between \( a^{2} \) and \( ab \) is also a multiple of \( n \). We will use a direct proof for this.

Assume a congruent modulo

Since \( a \equiv b(\bmod n) \), this implies that \( a = b + kn \), for some integer \( k \). This comes from the definition of congruence modulo \( n \).

Proof of Claim

Now, let's compute the difference between \( a^{2} \) and \( ab \). \nFrom \( a = b + kn \), we get \( a^{2} = (b + kn)^{2} = b^{2} + 2bkn + k^{2}n^{2} \). \nAnd compute the difference \( a^{2} - ab = b^{2} + 2bkn + k^{2}n^{2} - ab = b^{2} - ab + 2bkn + k^{2}n^{2} \). \nFactor out \( n \) to yield \( a^{2} - ab = n(bk + kn + k^{2}n) \). \nFherefore since \( a^{2} - ab \) is a multiple of \( n \), we have \( a^{2} \equiv a b(\bmod n) \).

Conclusion

Since we have shown that if \( a \equiv b(\bmod n) \), then \( a^{2} \equiv a b(\bmod n) \), the original claim has been proven directly.

Key concepts

Congruence Modulo

Congruence modulo is a fundamental concept in number theory that is used to describe when two numbers have the same remainder when divided by a given number. In mathematical terms, two integers a and b are said to be congruent modulo n, written as \( a \equiv b(\bmod n) \), if n divides their difference, meaning there exists an integer k such that \( a - b = kn \).

Applying this concept to our exercise, we're given that \( a \equiv b(\mod n) \). This provides the foundation for the proof, as it sets up the relationship between a and b under the modulus n. This congruence relation is an equivalence relation and it partitions the set of integers into equivalence classes or residue classes. This is incredibly useful in simplifying complex problems, as it allows for the manipulation of numbers within these classes, making computations more manageable.

In arithmetic, the concept becomes very practical. For instance, when considering time on a 12-hour clock, the numbers '13' and '1' are congruent modulo 12, because they represent the same position on the clock face despite being numerically different. The principle of solving problems involving congruence lies in this ability to regard numbers as ‘the same’ when they leave the same remainder after division by the modulus.

Direct Proof

A direct proof is a straightforward method of proving mathematical statements where we start from known facts or assumed premises and use logical steps to arrive at the conclusion. This style of proof is characterized by a direct connection between the premises and the conclusion, often using definitions, theorems, and axioms without appeal to contraries or contradiction.

In the context of our exercise, direct proof begins by assuming the given condition \( a \equiv b(\mod n) \), which means that \( a \) and \( b \) have the same remainder when divided by \( n \). We then show that under this assumption, the relationship \( a^2 \equiv ab(\mod n) \) must also be true. We do this by manipulating the expression involving \( a \) and \( b \) in a way that is allowed by algebraic rules and properties of congruence modulo, to demonstrate the end result.

In the step-by-step solution, the direct proof involves taking the expression \( a^2 - ab \) and factoring out the modulus \( n \) to show that this difference is also divisible by \( n \), confirming that the two expressions are indeed congruent modulo \( n \). It does not require assuming any opposite or negated forms, making it a more 'positive' approach to proving the statement.

Contrapositive Proof

In contrast to direct proofs, a contrapositive proof works by proving the contrapositive statement of the original proposition. For any implication of the form 'If P, then Q,' the contrapositive is 'If not Q, then not P.' If the contrapositive is true, then the original statement is also true, since in logic, a statement and its contrapositive are logically equivalent.

To apply contrapositive reasoning to the textbook exercise as an example, we would consider the contrapositive statement: If it is not true that \( a^2 \equiv ab(\mod n) \), then it is not true that \( a \equiv b(\mod n) \). In the case of our exercise, we selected direct proof as the preferable approach because it was more straightforward to prove the positive claim directly rather than via its negation.

However, contrapositive proof can be especially useful when the direct proof approach is cumbersome or when negating the conclusion leads to an easier proof. It is an important technique in a mathematician's toolkit and is often used for proofs involving inequalities or continuous functions. Knowing when to use a contrapositive proof can make some challenging problems much more tractable.