Modular Multiplicative Inverse

Given two integers a and m, find the modular multiplicative inverse of a modulo m - an integer x in the range [0, m-1] such that (a * x) mod m = 1. The inverse exists if and only if a and m are coprime (gcd(a, m) = 1). If no inverse exists, print -1 instead.

Input: A single line containing two space-separated integers a and m. Output: Print the modular inverse of a modulo m as an integer in [0, m-1], or -1 if it does not exist.

1 <= a < m <= 10^9 (m is not necessarily prime)

This is a foundational building block for modular arithmetic in general, including 'division' under a modulus (which isn't directly defined, but achieved by multiplying by the modular inverse instead) - used directly in problems like Binomial Coefficient Modulo a Prime.

Find the number that, when multiplied by a given value modulo m, gives exactly 1. Brute force: Try every value from 0 to m-1 directly, checking if (a * x) mod m equals 1 - this costs O(m), far too slow for m up to 10^9. Optimised: The Extended Euclidean Algorithm computes the GCD AND the coefficients (x, y) satisfying Bezout's identity (a*x + m*y = gcd) in the SAME O(log(min(a,m))) time as plain Euclid's algorithm - when gcd(a,m)=1, that same x IS the modular inverse (after normalizing into the valid range), no separate search needed.

1. Use the EXTENDED EUCLIDEAN ALGORITHM to find integers x, y such that a*x + m*y = gcd(a, m). 2. An inverse exists ONLY when gcd(a, m) = 1 (a and m are coprime); in that case, the x found is the answer (after adjustment). 3. The x produced may be NEGATIVE - add m and take mod m again to normalize it into the range [0, m-1].

Time: O(log(min(a,m))) - the extended Euclidean algorithm converges as fast as the plain version. Space: O(1) iteratively, or O(log(min(a,m))) stack frames if implemented recursively.

If gcd(a, m) != 1, no inverse exists - print -1 (this includes any case where a and m share a common factor greater than 1). If a = 1, the inverse is always 1 for any m > 1.

Be ready to explain WHY an inverse only exists when gcd(a,m)=1 - if they share a common factor, no multiple of a can ever land exactly on 1 modulo m, since every multiple of a would also share that common factor with m.