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

Printable View

- Feb 2nd 2010, 07:14 AMDeepucongruence in integer
if [a]=[1] in Zn, prove that (a,n)=1. Show by example that the converse may be false.

- Feb 2nd 2010, 01:04 PMDrexel28
I assume that $\displaystyle [z]=\left\{m\in\mathbb{Z}:m\equiv z\text{ mod }n\right\}$ and $\displaystyle \mathbb{Z}n=\mathbb{Z}_n$. If, so assume that $\displaystyle [a]=[1]\implies a\in[1]\implies a\equiv 1\text{ mod }n\implies a=zn+1\implies a+z'n=1$ where $\displaystyle z'=-z$. The conclusion follows from basic knowledge about linear Diophantine equations.

- Feb 2nd 2010, 06:43 PMtonio