Proof That Numbers are Equivalent mod n if and only if The Have the Same Remainder on Division by n
\[a \equiv b \; (mod \; n)\]
if and only if \[a, \; b\]
have the same remainder when divided by \[n\]
.Proof
Suppose
\[a, \; b\]
have the same remainder when divided by \[n\]
.\[a=qn+r, \; b=pn+r, \; 0 \le r \lt n\]
Then
\[a-b=*q-p)n \rightarrow a \equiv b \; (mod \; n)\]
.Conversely suppose
\[q \equiv b \; (mod \; n)\]
so \[a=b+kn, \; k \in \mathbb{N}\]
. Let \[b\]
have remainder \[r\]
when divided by \[n\]
so \[b=qn+r, \; 0 \le r \lt n\]
. Then\[a=b+kn=nq+r+kn=(q+k)n+r\]
The
\[a\]
has the same remainder on division by \[n\]
as \[b\]
. 
