0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – mlc Mar 25 '17 at 14:41
  • $\begingroup$ @mlc I am studying for the first time discrete mathematics, I don't understand your advice. I will edit the title of this question $\endgroup$ – user4789408 Mar 25 '17 at 14:44
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ If I want to compare integer with reals I can think in this way: in real numbers is the x that divides the a and has a result of 1 , in integer numbers is the x that multiplies the a and has a rest of 1 in module n. Is that correct? $\endgroup$ – user4789408 Mar 25 '17 at 15:02
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.