# Math Help - congruence in integer

1. ## congruence in integer

if [a]=[1] in Zn, prove that (a,n)=1. Show by example that the converse may be false.

2. Originally Posted by Deepu
if [a]=[1] in Zn, prove that (a,n)=1. Show by example that the converse may be false.
I assume that $[z]=\left\{m\in\mathbb{Z}:m\equiv z\text{ mod }n\right\}$ and $\mathbb{Z}n=\mathbb{Z}_n$. If, so assume that $[a]=[1]\implies a\in[1]\implies a\equiv 1\text{ mod }n\implies a=zn+1\implies a+z'n=1$ where $z'=-z$. The conclusion follows from basic knowledge about linear Diophantine equations.

3. Originally Posted by Deepu
if [a]=[1] in Zn, prove that (a,n)=1. Show by example that the converse may be false.

$(3,7)=1\,\,\,but\,\,\,[3]\neq [7]\,\,\,in\,\,\,\mathbb{Z}_7$

Tonio