Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 37 · Modular Arithmetic and CRT

CRT for Non-Coprime Moduli and Garner's Algorithm

Solve congruence systems whose moduli share factors, detect inconsistency with gcd, and reconstruct big integers from residues with Garner's mixed-radix algorithm.

The basic Chinese remainder theorem needs pairwise coprime moduli. Real problems rarely oblige: you might need x ≡ 4 (mod 6) and x ≡ 10 (mod 8), where gcd(6, 8) = 2. Sometimes there is a solution (it is unique modulo the lcm), and sometimes there is none. This lesson gives a complete answer and then shows Garner's algorithm, which rebuilds a big integer from small residues without ever touching a number larger than the answer.

Two congruences with a common factor

Take x ≡ a (mod m) and x ≡ b (mod n) and let g = gcd(m, n).

Theorem. The system is solvable if and only if a ≡ b (mod g). When solvable, the solution is unique modulo lcm(m, n) = mn/g.

Why. Any solution has x − a divisible by m, so x ≡ a (mod g), and likewise x ≡ b (mod g). So a ≡ b (mod g) is necessary. For sufficiency write x = a + mt. We need a + mt ≡ b (mod n), that is mt ≡ b − a (mod n). This linear congruence is solvable exactly when g | (b − a) (see the lesson on linear congruences), and its solutions form one class modulo n/g. Substituting, x is determined modulo m · (n/g) = lcm(m, n). ∎

Python Combine two congruences, coprime or not

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 first line reports x ≡ 10 (mod 24); the brute-force list shows 10 and 34. The second system is impossible: x ≡ 1 (mod 6) forces x to be odd, while x ≡ 2 (mod 8) forces it to be even.

Many congruences: fold from the left

For a list of congruences, combine the first two into one congruence (modulo their lcm), then combine the result with the third, and so on. If any step fails, the entire system has no solution.

Python General CRT

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.

A classic puzzle: a number leaves remainder 1 when divided by 2, 2 when divided by 3, 3 when divided by 4, 4 when divided by 5, 5 when divided by 6 and 0 when divided by 7. The first five conditions say x ≡ −1 modulo each, so x ≡ −1 (mod 60) and the seventh gives x = 119.

Python The classic puzzle

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.

Garner's algorithm

Suppose you hold x as residues r₁, ..., rₖ modulo pairwise coprime m₁, ..., mₖ and want the integer x. The textbook formula builds numbers as large as M². Garner's algorithm writes x in a mixed-radix form

x = v₁ + v₂m₁ + v₃m₁m₂ + ... + vₖm₁···mₖ₋₁, with 0 ≤ vᵢ < mᵢ

and finds the coefficients one at a time, always working modulo a single small mᵢ. It is the standard method for converting from residues to a number in big-integer libraries and in number-theoretic transforms.

Step i: reduce the partial value so far modulo mᵢ, then solve for vᵢ using the inverse of m₁···mᵢ₋₁ modulo mᵢ.

Python Garner's mixed-radix reconstruction

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.

Garner returns the mixed-radix digits and the reconstructed 12,345,678, which is less than the product of the moduli, so it is recovered uniquely. This is how a huge integer can be stored as a handful of machine-word residues: add and multiply residue by residue, and convert back at the end.

Python Big-number arithmetic with residues

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.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. When is x = a (mod m), x = b (mod n) solvable?

    Both congruences force x to have the same remainder modulo g = gcd(m, n), so a and b must agree mod g.
  2. 2. A solvable system with moduli 6 and 8 has a unique solution modulo what?

    The solution is unique modulo lcm(6, 8) = 24.
  3. 3. Which system has no solution?

    gcd(4, 6) = 2: 1 and 2 differ mod 2 (odd versus even).
  4. 4. What is the advantage of Garner's algorithm?

    All intermediate computations stay below the individual moduli.

Summary

  • For moduli with common factor g = gcd(m, n), the pair x ≡ a (mod m), x ≡ b (mod n) is solvable exactly when a ≡ b (mod g), with solution unique mod lcm(m, n).
  • For several congruences, combine them two at a time; any failure means no solution.
  • Garner's algorithm turns residues into mixed-radix digits and then into the integer, keeping intermediate values small.
  • Residue representations allow big-number arithmetic component by component, if the final answer is below the product of the moduli.

Next: Wilson's Theorem and Everyday Modular Applications