Question

Prove the following statements using either direct or contrapositive proof. If \(a \equiv b(\bmod n),\) then \(a\) and \(b\) have the same remainder when divided by \(n .\)

Short answer

The given proposition is true. If \(a \equiv b(\bmod n)\), then \(a\) and \(b\) always yield the same remainder when divided by \(n\), as proven by direct and contrapositive proofs.

Step-by-step solution

Understanding Modulo Equivalence

Let's first understand what it means when we say \(a \equiv b(\bmod n)\). In the context of modulo arithmetic, it means \(n\) divides the difference of \(a\) and \(b\), or equivalently, \(a - b = k*n\) where \(k\) is an integer.

Using the Division Algorithm

Next, we employ the division algorithm, which tells us that for any integer \(a\) and positive integer \(n\), there exist unique integers \(q\) and \(r\) (with \(0 \leq r < n)\), such that \(a = qn + r\). So, rewrite \(a\) and \(b\) in this form: \(a = q1*n + r1\) and \(b = q2*n + r2\).

Substituting into the Modulo Equation

Substitute these representations into the equation \(a - b = k*n\) from Step 1. We get: \((q1*n + r1) - (q2*n + r2) = k*n\), that simplifies into \((q1 - q2)*n + r1 - r2 = k*n\).

Deriving Equal Remainders

Here, notice that \((q1 - q2)*n\) and \(k*n\) are multiples of \(n\). Hence, for the equation to hold true, the difference of remainders \((r1 - r2)\) must also be a multiple of \(n\). However, \(0 \leq r1, r2 < n\). Thus, the only possible solution is \(r1 - r2 = 0\). This indicates that remainders are the same, \(r1 = r2\). Then, we have showed that \(a\) and \(b\) indeed yield the same remainder when divided by \(n\).

Direct and Contrapositive Proofs

This explanation includes both direct and contrapositive proofs. The direct proof is in the steps 1 through 4, where we started with the assumption that \(a \equiv b(\bmod n)\) and proved that \(a\) and \(b\) leave the same remainder when divided by \(n\). The contrapositive proof would assume that \(a\) and \(b\) do not leave the same remainder when divided by \(n\) and then prove that \(a \not\equiv b(\bmod n)\). The steps are similar but in reverse order.