Show that an inverse of a modulo m does not exist if gcd(a, m) > 1.
This means we have : where k is an integer. i.e.
By Bézout's identity, we know that :
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.