# why inverse of a number module n exists if gcd(number, module) = 1?

I have difficulties thinking the relationship between inverse of a number and gcd.

If I want to know if a specific number module n has an inverse I check if gcd between the number and the module is 1, why?

a≡b(n) has inverse only if  gcd(a,n)=1


I know that the result of gcd(a,n) is the rest of Euclidean division, why does it prove that a has an inverse module n?

• Welcome to math.SE. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. – mlc Mar 25 '17 at 14:41
• @mlc I am studying for the first time discrete mathematics, I don't understand your advice. I will edit the title of this question – user4789408 Mar 25 '17 at 14:44

This is because of Bézout's Identity: for $n, m \in {\mathbb Z}$ there are $x, y \in {\mathbb Z}$ such that $x n + y m = \gcd(n,m)$.
Applying this to $n$ and $m$ that have greatest common divisor 1, you get that there are $x, y$ such that $x n + y m = 1$. So, in particular, $x n \equiv 1 \pmod m$, which means that $n$ is invertible modulo $m$.
To actually find the $x, y$ from Bézout's Identity, use the Extended Euclidean Algorithm.
That is because of Bézout's identity: $\gcd(a,n)=1$ if and only if there exist $u,v\in\mathbf Z$ such that $ua+vn=1$. Reducing this relation modulo $n$ yields $$u\bmod n\cdot a\bmod n\equiv 1\bmod n.$$ Conversely, if $a$ has an inverse $u$ mod $n$, it leans there exists $b\in \mathbf Z$ such that $$ua=1+bn,\enspace\text{whence}\quad ua-bn=1,$$ which proves $a$ and $n$ are coprime.