Question

Question: If$\left[a\right]\mathbf{=}\left[1\right]$ in ${\mathrm{\mathbb{Z}}}_n$, prove that $\left(a,n\right)\mathbf{=}\mathbf{1}$. Show by example that the converse may be false.

Short answer

Answer:

It is proved that $\left(a,n\right)=1$. It is verified by example that the converse is false.

Step-by-step solution

Prove that (a, n) = 1 

It is given that$\left[a\right]=\left[1\right]$in ${\mathrm{\mathbb{Z}}}_n$.

According to Division Algorithm, there exist unique integers and such that$\mathit{a}\mathbf{=}\mathit{b}\mathit{q}\mathbf{+}\mathit{r}\mathbf{,}\mathbf{0}\mathbf{⩽}\mathit{r}\mathbf{<}\mathit{b}$, where a and b are integers with the condition b > 0 .

This implies that for some integer , we have $a=np+1$.

Let d be a divisor of a and n .This implies that d divides a and ,nk that is ,d divides their difference$d|\left(a-nk\right)$,but we have$a-nk=1$. This means that d divides 1.

Therefore, any common divisor of and must be 1, that is,$\left(a,n\right)=1$ .

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

Show by example that the converse may be false

Consider [5] in ${\mathrm{\mathbb{Z}}}_6$. Find the value of (5,6) .

(5,6)=1

But we can observe that $\left[5\right]\ne \left[1\right]$.

Hence,it is verified by example that the converse is false.