Show that an inverse ofamodulomdoes not exist ifgcd(a, m) > 1.

Printable View

- Oct 18th 2008, 09:46 PMaaronrjInverse Modulus Proof
Show that an inverse of

*a***modulo***m*does not exist if**gcd**(*a, m*) > 1. - Oct 18th 2008, 11:54 PMMoo
Hello,

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

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

By Bézout's identity, we know that :

$\displaystyle \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.