Skip to content
Tutorials Center
My learning

Topics

Lesson 190 of 225 ยท Math and Bit Manipulation

Chinese Remainder Theorem and Modular Inverse

Compute modular inverses with the extended Euclidean algorithm and solve systems of congruences with the Chinese Remainder Theorem, including non-coprime moduli, in Python.

Many problems give you remainders instead of numbers: "a number leaves 2 when divided by 3, 3 when divided by 5, and 2 when divided by 7. What is it?" That puzzle is more than 1,500 years old, and its general solution is the Chinese Remainder Theorem (CRT). It says that if you know a number's remainders modulo several pairwise coprime numbers, you know the number itself modulo their product.

To use CRT you need one more tool: the modular inverse, the "division" of modular arithmetic. Both rest on the extended Euclidean algorithm, so we start there. If you need a refresher on gcd and pow(a, b, m), read number theory basics and fast exponentiation first.

The extended Euclidean algorithm

Ordinary Euclid computes g = gcd(a, b). The extended version also finds integers x and y such that

a * x + b * y = g

This is called Bezout's identity. The numbers x and y can be negative. You get them by unwinding the recursion: if b * x1 + (a % b) * y1 = g, then, since a % b = a - (a // b) * b, we have a * y1 + b * (x1 - (a // b) * y1) = g.

Python Extended gcd and Bezout coefficients

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 recursion depth is O(log min(a, b)), the same as ordinary Euclid.

Modular inverse

The inverse of a modulo m is a number inv such that a * inv โ‰ก 1 (mod m). With it you can divide: b / a mod m is b * inv mod m.

An inverse exists exactly when gcd(a, m) = 1. Bezout gives it directly: if a * x + m * y = 1, then taking everything modulo m leaves a * x โ‰ก 1. So x mod m is the inverse.

There are two other ways you will see:

  • Fermat's little theorem (only when m is prime): inv = pow(a, m - 2, m).
  • Python 3.8+: pow(a, -1, m) does it for any modulus and raises ValueError if no inverse exists.
Python Three ways to get an inverse

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.

Modular division is what lets you compute binomial coefficients such as C(n, k) mod p, covered in combinatorics.

Solving two congruences

Take the system

TEXT
x โ‰ก 2 (mod 3)
x โ‰ก 3 (mod 5)

Every solution of the first has the form x = 2 + 3t. Substitute into the second: 2 + 3t โ‰ก 3 (mod 5), so 3t โ‰ก 1 (mod 5), and t โ‰ก inverse(3) * 1 = 2 (mod 5). Then x = 2 + 3 * 2 = 8, and all solutions are x โ‰ก 8 (mod 15).

This "merge two into one" step works for any two congruences, and repeating it merges as many as you like. The result lives modulo the product of the moduli (when they are pairwise coprime).

flowchart LR
    A["x โ‰ก 2 (mod 3)"] --> M1["merge"]
    B["x โ‰ก 3 (mod 5)"] --> M1
    M1 --> R1["x โ‰ก 8 (mod 15)"]
    R1 --> M2["merge"]
    C["x โ‰ก 2 (mod 7)"] --> M2
    M2 --> R2["x โ‰ก 23 (mod 105)"]

Merging congruences one pair at a time reduces the whole system to a single congruence.

The Chinese Remainder Theorem

Theorem. If m1, m2, ..., mk are pairwise coprime, then for any remainders r1, ..., rk the system x โ‰ก ri (mod mi) has exactly one solution modulo M = m1 * m2 * ... * mk.

The classic constructive formula: for each i, let Mi = M // mi and yi = inverse(Mi, mi). Then

x = (r1 * M1 * y1 + ... + rk * Mk * yk) mod M

Each term is 0 modulo every other modulus (because Mi contains them as factors) and equals ri modulo mi.

Generalizing to moduli that share factors

Real inputs often have moduli that are not coprime. The merge step handles it. To merge x โ‰ก r1 (mod m1) with x โ‰ก r2 (mod m2), let g = gcd(m1, m2):

  • If (r2 - r1) % g != 0, the system has no solution.
  • Otherwise the merged modulus is lcm(m1, m2), and you solve m1 * t โ‰ก r2 - r1 (mod m2) by dividing everything by g.
Python Merge congruences, with or without common factors

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 crt([5, 11], [12, 18]) returns a modulus of 36, not 216: the lcm, not the product.

Using CRT in practice

Big numbers from small remainders. If you must compute a result modulo a huge M but the arithmetic is easier modulo small coprime primes, compute the answer modulo each prime and combine with CRT. This is how some libraries multiply very large integers, and how the FFT lesson recovers exact values using several moduli.

Counting problems with a composite modulus. To compute C(n, k) mod a composite m, factor m into prime powers, solve each separately, and glue the answers with CRT.

Scheduling and cycles. "Event A repeats every 4 days starting on day 1, event B every 6 days starting on day 2. When do they coincide?" That is exactly the conflicting system above: they never do.

Cryptography. RSA decryption is about four times faster when done modulo p and q separately, then recombined with CRT.

Python Reconstruct a number from remainders

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.

Common mistakes

  • Forgetting to reduce. Always reduce remainders (r % m) and keep the result in [0, M); Python's % already gives a non-negative result.
  • Assuming coprime moduli. Check the gcd. If it is not 1, the answer may not exist, and when it does the modulus is the lcm.
  • Using Fermat's inverse with a composite modulus. pow(a, m - 2, m) is only valid when m is prime. Use pow(a, -1, m) or extended gcd.
  • Asking for an inverse when gcd(a, m) > 1. It does not exist; handle the error.
  • Integer overflow in other languages. Python integers never overflow, but C++ and Java need 128-bit products when M is large.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. When does a modular inverse of a modulo m exist?

    If a and m share a factor, a * x mod m always shares it too and can never equal 1.
  2. 2. What does the extended Euclidean algorithm return in addition to gcd(a, b)?

    These are the Bezout coefficients; x modulo m is the inverse of a when the gcd is 1.
  3. 3. The system x = 1 (mod 4) and x = 2 (mod 6) has no solution. Why?

    Two congruences are compatible only when the gcd of the moduli divides the difference of the remainders.
  4. 4. For pairwise coprime moduli 3, 5 and 7, the solution of the CRT system is unique modulo what?

    The unique solution lives modulo the product of all moduli, 3 * 5 * 7 = 105.
  5. 5. Which expression is NOT a safe way to compute the inverse of a modulo a composite m?

    Fermat's little theorem needs a prime modulus. For composite m it can give a wrong result.

Summary

  • The extended Euclidean algorithm finds x, y with a*x + b*y = gcd(a, b) in O(log n) steps.
  • The inverse of a mod m exists only when gcd(a, m) = 1; get it from extended gcd, pow(a, -1, m), or pow(a, m - 2, m) when m is prime.
  • CRT: remainders modulo pairwise coprime moduli determine one number modulo their product.
  • To merge general congruences, check that the gcd divides the difference; the result is modulo the lcm.
  • CRT lets you work with small moduli and recombine, which appears in counting, cryptography and polynomial multiplication.

Next: FFT and Polynomial Multiplication