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