GCD & Modular Arithmetic

Modular Inverse

You cannot divide under a modulus, so multiply by the inverse instead. When the modulus is prime, Fermat's little theorem gives the inverse of a as a^(m-2) mod m, computed with fast exponentiation. This is how every 'answer mod 1e9+7' division problem is actually solved.

O(log m)

O(1)

say this out loud

I cannot divide under a modulus, so I multiply by the inverse. The modulus is prime, so Fermat gives the inverse as a to the power m minus two.

How It Works

Modular arithmetic passes cleanly through addition, subtraction and multiplication, but not division: (a / b) mod m is not (a mod m) / (b mod m). The fix is to replace division with multiplication by the modular inverse, the value x where b * x mod m equals 1.

When the modulus is prime, and competitive problems almost always pick 10^9 + 7 precisely because it is, Fermat's little theorem gives the inverse directly: a^(m-1) mod m is 1 for any a not divisible by m, so a^(m-2) is the inverse. That means one call to fast exponentiation, O(log m), and no extra machinery. If the modulus is not prime, Fermat does not apply and you need the extended Euclidean algorithm, which works whenever a and m are coprime. Knowing which of the two applies, and why, is the part interviewers probe.

Step-by-Step Visualization

Compute 1 divided by 3, modulo 7

1/8

Code

Java

static final long MOD = 1_000_000_007L;

// Valid only because MOD is prime (Fermat's little theorem)
static long modInverse(long a) {
  return modPow(a, MOD - 2, MOD);
}

// (a / b) mod MOD  becomes  a * inverse(b) mod MOD
static long divide(long a, long b) {
  return a % MOD * modInverse(b) % MOD;
}

Tips & Gotchas

1Fermat only applies when the modulus is prime, which 1e9+7 is

2inverse(a) = a^(m-2) mod m, computed with the same fast exponentiation

3For a non-prime modulus use the extended Euclidean algorithm instead

Practice Problems

1Number of Ways to Divide a Long Corridor
2Count Anagrams
3Distinct Prime Factors of Product of Array
4Number of Music Playlists

About the GCD & Modular Arithmetic Pattern

Modular arithmetic is what lets you answer questions about enormous numbers without ever holding one. Addition and multiplication pass through the modulus cleanly, division does not, and the Euclidean algorithm underpins the whole area.

Key insight

Almost every math problem is asking you to avoid the obvious loop. Trial division to n becomes a sieve, repeated multiplication becomes binary exponentiation, and division under a modulus becomes multiplication by an inverse. If your solution loops to n or to the exponent, there is nearly always a log or sqrt version.

Common Math & Number Theory Interview Problems

Count Primes
Pow(x, n)
Greatest Common Divisor of Strings
Excel Sheet Column Title
Ugly Number II
Factorial Trailing Zeroes

Frequently Asked Questions

Why does Fermat's little theorem require a prime modulus?

The theorem states a^(m-1) mod m equals 1 for prime m and a not divisible by m. That identity is what lets you rewrite the inverse as a^(m-2). For composite m the identity fails, so the formula silently returns a wrong value rather than an error, which makes it a nasty bug to find.

What if the modulus is not prime?

Use the extended Euclidean algorithm, which finds x and y satisfying ax + my = gcd(a, m). When the gcd is 1, x is the inverse. It works for any modulus coprime to a, and if the gcd is not 1 then no inverse exists at all.

Do I need one modPow call per division?

Not if you plan ahead. For factorial-heavy problems, compute the inverse of the largest factorial once and derive every smaller inverse factorial by multiplying downward. That turns n inversions into one, which matters when n is a million.