Let \(a,b,n \in \mathbb{Z}\) with \(n > 0\). Show that \(a \equiv b \pmod n\) if and only if \((a \bmod n) = (b \bmod n) \).

Let \(r_a = a \bmod n\), and \(r_b = b \bmod n \), such that

\[ \begin{aligned} a &= x_an + r_a \text{ for some unique } x_a,r_a \in \mathbb{Z} \text{ with } 0 \le r_a \lt n\\ b &= x_bn + r_b \text{ for some unique } x_b,r_b \in \mathbb{Z} \text{ with } 0 \le r_b \lt n \\ a - b &= n(x_a - x_b) + (r_a - r_b) \end{aligned} \]

\(\implies\)

\(\mspace20pt\) Assume \(a \equiv b \pmod n\), and note that \(0 \le |r_a - r_b| \lt n\). This means \(n \mid a - b\), which only makes sense if:

\[ \begin{aligned} r_a - r_b &= 0 \\ r_a &= r_b \\ \end{aligned} \]

\(\mspace20pt\) Thus \((a \bmod n) = (b \bmod n)\).

\(\impliedby\)

\(\mspace20pt\) The reverse is obvious. Assume \((a \bmod n) = (b \bmod n) \), \(r_a - r_b\) must be zero. So

\[ \begin{aligned} a - b &= n(x_a - x_b) + (r_a - r_b) \\ a - b &= n(x_a - x_b) \end{aligned} \]

\(\mspace20pt\) Thus \(a \equiv b \pmod n\).

\(\Box\)

# posted by rot13(Unafba Pune) @ 11:08 PM