Question

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

Short 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$q$ and$r$ such that$a=bq+r,0\le r<b$ , where$a$ and$b$ are integers with the condition $b>0$.

This implies that for some integer$p$ , 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 $\overline{)d}\left(a-nk\right)$, but we have $a-nk=1$. This means that$d$ divides 1.

Therefore,any common divisor of$a$ and$n$ 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 $\left[5\right]$in ${\mathrm{\mathbb{Z}}}_6$. Find the value of $\left(5,6\right)$.

$\left(5,6\right)=1$

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

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