Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 68 · Number Theory

Modular Arithmetic

Learn congruences and residues, do clock arithmetic, use Python's pow(a, b, m) for fast powers, compute modular inverses and solve linear congruences.

Modular arithmetic is arithmetic on a clock. If it is 10 o'clock and you wait 5 hours, the clock shows 3, not 15, because after 12 the numbers wrap around. Replacing "the number" by "the remainder after division" turns an infinite number line into a finite loop, and that loop is the natural setting for hash tables, calendars, checksums, random number generators and almost all of modern cryptography.

In this lesson you will learn the language of congruences, see that addition and multiplication still work after wrapping, compute huge powers instantly with pow(a, b, m), find modular inverses (the "division" of this world), and solve linear congruences. The tools come from GCD, LCM and the Euclidean Algorithm.

Congruences and residues

We say a is congruent to b modulo m, written a ≡ b (mod m), when m divides a − b. Equivalently, a and b leave the same remainder when divided by m. So 17 ≡ 2 (mod 5) because 5 divides 15, and also 17 ≡ −3 (mod 5).

The residue of a modulo m is the remainder a % m, a number from 0 to m − 1. Every integer is congruent to exactly one residue, so modulo m there are exactly m "different" numbers: 0, 1, ..., m − 1. Congruence is an equivalence relation (reflexive, symmetric, transitive), and its classes are the residue classes, which you will meet again in Equivalence Relations and Partial Orders.

Python's % operator always returns a result with the same sign as the divisor, so with a positive modulus the result lies in 0 to m − 1 even for negative numbers. Many other languages return a negative remainder instead, which is a common source of bugs when code is ported.

Python Residues and a 12-hour clock

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that -17 % 5 is 3, not −2: since −17 = 5·(−4) + 3, the residue is 3. A time of "12 o'clock" shows up as 0 here, a reminder that residues run from 0 to m − 1.

Adding and multiplying

The reason congruences are useful is that they respect the arithmetic operations. If a ≡ a' and b ≡ b' (mod m), then

  • a + b ≡ a' + b' (mod m)
  • a − b ≡ a' − b' (mod m)
  • a · b ≡ a' · b' (mod m)

So you can reduce the numbers first, or reduce at any point along the way, and the final residue does not change. A long product like 123456789 · 987654321 can be handled by multiplying small residues. This is what lets programs work with huge numbers while keeping every intermediate value small.

Rules that survive wrapping

Addition Reduce first or last, same result.
Multiplication Also safe to reduce early.
Powers Repeat multiplication, reducing every time.
Division Not automatic. Needs an inverse.
1 / 2

Division is the odd one out. In ordinary arithmetic 6 · 2 = 6 · 5 does not hold, but modulo 8 we have 4 · 2 = 8 ≡ 0 and 4 · 4 = 16 ≡ 0, so 4 · 2 ≡ 4 · 4 even though 2 ≢ 4. You cannot cancel the 4. We will see exactly when cancellation is allowed.

Fast powers with pow(a, b, m)

Computing a^b first and reducing afterwards is hopeless when b is large: 3^(10^18) has hundreds of quadrillions of digits. Instead reduce after every multiplication, and use repeated squaring so that only about log₂(b) multiplications are needed. Python builds this into pow with a third argument.

Python Modular exponentiation

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

pow(3, 10**18, 10**9 + 7) returns instantly, with the result 246336683. The hand-written power_mod shows the idea: look at the exponent in binary, square the base at every bit, and multiply it into the result when the bit is 1. The last-digit question is answered by the observation that powers of 7 repeat their last digit every four steps (7, 9, 3, 1), and 2024 is a multiple of 4.

Modular inverses

A modular inverse of a modulo m is a number x with a·x ≡ 1 (mod m). Having an inverse is what makes division possible: dividing by a means multiplying by x. The inverse exists exactly when gcd(a, m) = 1, and then it is unique modulo m. By Bezout's identity there are integers x and y with a·x + m·y = 1, and reducing modulo m gives a·x ≡ 1.

When m is not prime some nonzero residues have no inverse. Compare the multiplication tables below: modulo 7 every row contains a 1, modulo 8 the rows for 2, 4 and 6 do not.

Python Which numbers have inverses?

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Since Python 3.8, pow(a, -1, m) returns the inverse and raises ValueError when there is none. When m is prime, every nonzero residue is invertible, which is the reason finite fields such as the integers mod a prime are so well behaved. The count of invertible residues modulo m is Euler's totient φ(m): φ(12) = 4, matching the list above.

Solving linear congruences

A linear congruence is an equation a·x ≡ b (mod m). Let g = gcd(a, m).

  • If g does not divide b, there are no solutions.
  • If g divides b, divide everything by g: a'·x ≡ b' (mod m') with a' = a/g, b' = b/g, m' = m/g. Now gcd(a', m') = 1, so a' has an inverse and x ≡ b'·a'^(−1) (mod m').
  • That one residue modulo m' lifts to exactly g solutions modulo m: x0, x0 + m', x0 + 2m', and so on.
Python A linear congruence solver

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The four cases cover the whole story. 3x ≡ 5 (mod 7) has a single solution because 3 is invertible, 4x ≡ 8 (mod 12) has gcd 4 and four solutions, 4x ≡ 6 (mod 12) has none because 4 does not divide 6, and 6x ≡ 9 (mod 15) has three. Brute force confirms each answer.

When a problem asks for "the answer modulo 1,000,000,007", reduce after every addition or multiplication. Python's integers never overflow, but reducing keeps numbers small and fast.

Fermat, Euler and Wilson: the theorems and why they hold

Three classical theorems explain why modular arithmetic works so well, and each has a short proof you can follow.

Fermat's little theorem. If p is prime and p does not divide a, then a^(p-1) ≡ 1 (mod p).

Proof idea. Take the nonzero residues 1, 2, ..., p-1 and multiply each by a. The results a, 2a, ..., (p-1)a are all nonzero and all different mod p (if ia ≡ ja you could cancel a, because a has an inverse, and get i ≡ j). So they are the same p-1 residues in a different order. Multiplying them all gives a^(p-1) · (p-1)! ≡ (p-1)! (mod p), and since (p-1)! has no factor p, we can cancel it to get a^(p-1) ≡ 1.

Euler's theorem. For any n with gcd(a, n) = 1, a^φ(n) ≡ 1 (mod n), where φ(n) counts the residues coprime to n. The proof is the same shuffle applied only to the φ(n) residues coprime to n, which form a group. It is also a special case of Lagrange's theorem for the unit group Z_n^* (see groups).

Wilson's theorem. An integer p > 1 is prime if and only if (p-1)! ≡ -1 (mod p).

Proof idea for primes. In Z_p every nonzero residue has a unique inverse. The only residues that are their own inverse satisfy x² ≡ 1, so x ≡ ±1. In the product 1 · 2 ⋯ (p-1), every other residue pairs up with its different inverse and each pair contributes 1. What remains is 1 · (p-1) ≡ -1. For composite n, any proper divisor d of n satisfies d ≤ n-1, so d divides (n-1)!. If (n-1)! ≡ -1 (mod n) then d would divide -1, which is impossible for d > 1.

Wilson's theorem is a perfect primality test in principle, but computing a factorial is far too slow to use in practice. Fermat's theorem, in contrast, is the engine of modular inverses (a^(p-2) is the inverse of a mod p) and of fast primality tests. The tests are not perfect: a Carmichael number is a composite n with a^(n-1) ≡ 1 (mod n) for every a coprime to n, so it fools the plain Fermat test. The smallest is 561.

Python Checking the theorems and breaking the Fermat test

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice how 561, 1105 and 1729 pass the Fermat test with every base coprime to them yet are composite (561 = 3 · 11 · 17). Real primality testing therefore uses the stronger Miller-Rabin test, which closes this loophole with a few more steps.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What is -17 % 5 in Python?

    -17 = 5 * (-4) + 3, and Python returns a remainder with the sign of the divisor, so the result is 3.
  2. 2. Which statement about 4 * 2 and 4 * 4 modulo 8 is true?

    4 * 2 = 8 and 4 * 4 = 16 are both 0 mod 8, but 2 and 4 are not congruent. 4 has no inverse mod 8, so cancelling it is not valid.
  3. 3. When does a have an inverse modulo m?

    An inverse exists exactly when a and m are coprime, which follows from Bezout's identity.
  4. 4. How many solutions in range(12) does 4x = 8 (mod 12) have?

    gcd(4, 12) = 4 divides 8, so there are 4 solutions: 2, 5, 8 and 11.
  5. 5. Why is pow(3, 1018, 109 + 7) fast?

    Repeated squaring needs about log2(b) multiplications, each reduced modulo m, so the numbers never grow.

Summary

  • a ≡ b (mod m) means m divides a − b; a % m gives the residue in 0 to m − 1, even for negative a in Python.
  • Addition, subtraction and multiplication can be reduced at any stage without changing the result.
  • pow(a, b, m) computes huge powers quickly by repeated squaring.
  • a has an inverse modulo m exactly when gcd(a, m) = 1; pow(a, -1, m) finds it.
  • a·x ≡ b (mod m) has solutions only when gcd(a, m) divides b, and then it has gcd(a, m) of them.

Next: Number Bases and Representations, where residues turn into digits.