Show that an inverse of a modulo m does not exist if gcd(a, m) > 1.
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.