Compute the modular multiplicative inverse of a modulo m, i.e. the integer x in [0, m) with (a * x) mod m ==…

Question

Compute the modular multiplicative inverse of a modulo m, i.e. the integer x in [0, m) with (a * x) mod m == 1, or return -1 if no inverse exists (when gcd(a, m) != 1). Here m may NOT be prime, so Fermat's little theorem does not apply; use the extended Euclidean algorithm. By convention return 0 when m == 1.

Prep Room · Answer

**Intuition** The modular inverse of a mod m is x with a*x = 1 (mod m). It exists only when gcd(a, m) = 1. Since m need not be prime, Fermat's little theorem…

Modular inverse extended euclidean