# Math Help - Modulo Classes Problems

1. ## 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$.

2. 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.$