Question

Prove or disprove: If $\left[a\right]=\left[b\right]$in${\mathrm{\mathbb{Z}}}_n$ , then$\left(a,n\right)=\left(b,n\right)$ .

Short answer

It is proved that $\left(a,n\right)=\left(b,n\right)$.

Step-by-step solution

Prove that  a,n=b,n

Assume that $f=gcd\left(b,n\right)$. This means that $\overline{)f}b$and $\overline{)f}n$.

This implies that there exist integers x and y such that it satisfies $b=fw$and $n=fz$.

Since it is given that $\left[a\right]=\left[b\right]$in ${\mathrm{\mathbb{Z}}}_n$, this implies that $a\equiv b\left(modn\right)$, that is, $\overline{)n}\left(a-b\right)$.

Use the division Algorithm 

By Applyingthedivision algorithm, we have $a=pn+r$and $b=qn+r$, where $p,q$, and$r$ are integers with the condition$0\le r<n$ .

Therefore,

$\begin{array}{rcl}\left(a,n\right)& =& \left(pn+r,n\right)\\ & =& \left(r,n\right)\\ & =& \left(r+qn,n\right)\\ & =& \left(b,n\right)\end{array}$

Hence, it is proved that$\left(a,n\right)=\left(b,n\right)$ .