# Modulo Classes Problems

• Feb 8th 2009, 08:49 PM
akolman
Modulo Classes Problems
Hello, I need help with the following problem

Let $\displaystyle n \in \mathbb{N}$ and $\displaystyle a \in \mathbb{Z}$, so $\displaystyle [a] \in \mathbb{Z}_n$. Prove that there exists an integer $\displaystyle b$ such that $\displaystyle [a][b]=[1]$ if and only if $\displaystyle gcd(a,n)=1$.
• Feb 9th 2009, 06:50 AM
clic-clac
Hi

That can be done using the fact that if $\displaystyle n$ and $\displaystyle m$ are two integers, $\displaystyle gcd(n,m)=1 \Leftrightarrow \exists u,v\in\mathbb{Z}\ \text{such that}\ un+vm=1.$ (Bezout's identity)

$\displaystyle gcd(a,n)=1\Rightarrow \exists u,v\in \mathbb{Z}\ \text{s.t.}\ ua+vn=1$ so $\displaystyle b=u$ is a solution.

$\displaystyle \exists b\in\mathbb{Z}\ \text{s.t.}\ [a][b]=1\Rightarrow \exists k\in\mathbb{Z}\ ab-1=kn\Rightarrow \exists u,v\in\mathbb{Z}\ \text{s.t.}\ ua+vn=1$ (with $\displaystyle u=b$ and $\displaystyle v=-k$) therefore $\displaystyle gcd(a,n)=1.$