Question

Prove that$a\equiv b\left(modn\right)$ if and only if$a$ and$b$ leave the same remainder when divided by $n$.

Short answer

It is proved that $a\equiv b\left(modn\right)$if and only if$a$ and$b$ have the same remainder when divided by$n$ .

Step-by-step solution

Prove that if  a≡n mod nthen a and b leave the same remainder when divided by n. 

Let us consider the integers a,$b$and $n$, which satisfy the relation $a\equiv b\left(modn\right)$. This means that there exists an integer $k$, which holds the property

$a-b=nk$.



Let $a\equiv b\left(modn\right)$, then $\left(a-b\right)\left(modn\right)\equiv 0$. This implies that there exists an integer $k$such that

$\begin{array}{rcl}a-b& =& nk\\ a& =& nk+b\end{array}$.

Consider$b$leaves remainder$r$when divided by$n$. Then, $b=nq+r$, where$q$is an integer.

Use this value into equation $a=nk+b$ as follows:

$\begin{array}{rcl}a& =& nk+b\\ & =& nk+nq+r\\ & =& n\left(k+q\right)+r\end{array}$

This implies that the remainder of$a$when divided by $n$is$r$. Thus,$a$and$b$have the same remainder.

Hence, it is proved that if$a\equiv b\left(modn\right)$, then $a$and $b$have the same remainder.

Prove that if a and b leave the same remainder when divided by n , then a≡n mod n. 

Consider that $a$and $b$have the same remainder when divided by $n$. This implies that $a=np+r$and $b=nq+r$, where $q,p$ are integers.

Find the value of $a-b$as follows:

$\begin{array}{rcl}a-b& =& np+r-nq-r\\ & =& np-nq\\ & =& n\left(p-q\right)\end{array}$

This implies that$\left(a-b\right)\left(modn\right)\equiv 0$ , that is,$a\equiv b\left(modn\right)$ .



Hence, it is proved that $a\equiv b\left(modn\right)$if and only if$a$ and $b$have the same remainder when divided by$n$ .