# Modulo Classes Problems

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

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

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

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

$\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 $u=b$ and $v=-k$) therefore $gcd(a,n)=1.$