# Inverse Modulus Proof

• October 18th 2008, 09:46 PM
aaronrj
Inverse Modulus Proof
Show that an inverse of a modulo m does not exist if gcd(a, m) > 1.
• October 18th 2008, 11:54 PM
Moo
Hello,
Quote:

Originally Posted by aaronrj
Show that an inverse of a modulo m does not exist if gcd(a, m) > 1.

b is an inverse of a modulo m if $ab \equiv 1 (\bmod m)$

This means we have : $ab=1+mk$ where k is an integer. i.e. $ab-mk=1$

By Bézout's identity, we know that :
$\exists u,v \in \mathbb{Z} \text{ such that } au+bv=1 \Leftrightarrow \text{gcd}(a,b)=1$
it appears in the French wikipedia and I've been taught this, but I don't know where to find it in English (not in wikipedia nor in mathworld). If you want a proof, tell me.

And you're done.