# congruence in integer

• February 2nd 2010, 08:14 AM
Deepu
congruence in integer
if [a]=[1] in Zn, prove that (a,n)=1. Show by example that the converse may be false.
• February 2nd 2010, 02:04 PM
Drexel28
Quote:

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.
• February 2nd 2010, 07:43 PM
tonio
Quote:

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