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

Printable View

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

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

b is an inverse of a modulo m if

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.