Modular inverse

Lesson 2 could add, subtract and multiply remainders, but not divide. This lesson shows when division modulo m is possible, three ways to do it, and how to solve several “x leaves this remainder” conditions at once.

Dividing on a clock

Dividing by a is the same as multiplying by a number that undoes multiplying by a. Modulo m, such a number is called an inverse of a:

Modulo 7, the inverse of 3 is 5, because 3 · 5 = 15 = 2 · 7 + 1. So “divide by 3” modulo 7 means “multiply by 5”: 6 / 3 = 2, and indeed 6 · 5 = 30, which leaves 2. Step through the tables in the figure.

When does an inverse exist? Exactly when gcd(a, m) = 1, that is, when a and m have no common divisor above 1. If they share a divisor g above 1, then a · y − q · m is a multiple of g for every y and q, so it is never 1. If gcd(a, m) = 1, the next section finds the inverse. So modulo a prime p, every a from 1 to p − 1 has an inverse; modulo 8, only the odd numbers do.

Inverses from Euclid

Lesson 1’s extended algorithm finds x and y with a · x + m · y = gcd(a, m). If the gcd is 1, then a · x = 1 − m · y, which leaves 1 modulo m. So x is the inverse:

def inverse(a, m):
    g, x, _ = ext_gcd(a, m)      # lesson 1
    if g != 1:
        raise ValueError("no inverse")
    return x % m                 # x may be negative

inverse(3, 7)       # 5
pow(3, -1, 7)       # 5: built in, Python 3.8 and later

pow(a, -1, m) raises ValueError when there is no inverse. It works for any m, not only primes, and takes O(log m) steps, like Euclid’s algorithm.

Fermat’s little theorem

For a prime modulus there is a second way, from a rule found by Pierre de Fermat in 1640:

Here aᵖ⁻¹ means a to the power p − 1. Why? Look at the row of a in the modulo 7 table: a · 1, a · 2, …, a · (p − 1) leave the remainders 1 to p − 1, each exactly once, in a new order. (Two of them cannot be equal, because a has an inverse that would undo the difference.) So their product leaves the same remainder as 1 · 2 · … · (p − 1). That product is aᵖ⁻¹ · (p − 1)!, and (p − 1)! has an inverse, so it cancels and leaves aᵖ⁻¹ ≡ 1.

So a · aᵖ⁻² ≡ 1, and the inverse of a is pow(a, p - 2, p), one fast power (lesson 3). The rule also explains lesson 2’s warning about exponents: modulo a prime p, and for a base that p does not divide, an exponent may be reduced modulo p − 1.

Many inverses at once

Lesson 6 needs the inverses of many numbers modulo the same prime p. Calling pow for each costs O(log p) each. There is a rule that gives all the inverses of 1 to n in O(n):

Why? p = (p // i) · i + (p % i), so modulo p, 0 ≡ (p // i) · i + (p % i). Multiply both sides by inv[i] and by inv[p % i]: 0 ≡ (p // i) · inv[p % i] + inv[i]. Since p % i is smaller than i, its inverse is already known. For factorials there is an even simpler way: work out the inverse of n! once with pow, then go down, because the inverse of (i − 1)! is the inverse of i! times i.

The Chinese remainder theorem

A number leaves remainder 2 when divided by 3, and remainder 3 when divided by 5. What is it? The third version of the figure places each x from 0 to 14 by its two remainders, and every cell is hit exactly once.

Finding it. The numbers with x % m = r are r, r + m, r + 2m, …, that is, x = r + m · t. The second condition says m · t ≡ s − r (mod n). Since m has an inverse modulo n, t = (s − r) · inverse(m, n) % n. Then x = r + m · t, and adding any multiple of m · n gives the other solutions.

When the moduli share a divisor g = gcd(m, n), the two conditions must agree modulo g: x % 4 = 1 says x is odd, and x % 6 = 2 says x is even, so no x has both. If they agree, divide the equation for t by g, solve modulo n / g, and the answers repeat every lcm(m, n). Several conditions are combined one at a time: after each one, the answers are x, x + L, x + 2L, …, where L is the lcm of the moduli so far. MATH-P5 asks for exactly this.

Now try MATH-P5, The Chinese remainder theorem.