Course contentsShow
← Mathematics
Lesson 2755 of 3,12154. Number TheoryFree lesson

The CRT Construction Algorithm

Master the step-by-step method to construct a solution using products and modular inverses.

The CRT Construction Algorithm

You'll learn: The step-by-step algorithmic recipe for building the unique solution to systems of linear congruences guaranteed by the Chinese Remainder Theorem.

The Core Method

The Chinese Remainder Theorem tells us that a solution exists and is unique modulo the product of pairwise coprime moduli. But how do we actually construct it?

The CRT Construction Algorithm gives us the explicit formula. For a system like:

  • x ≡ a₁ (mod m₁)
  • x ≡ a₂ (mod m₂)
  • ...
  • x ≡ aₖ (mod mₖ)

where all mᵢ are pairwise coprime:

The Algorithm Steps

  1. Compute M = m₁ · m₂ · ... · mₖ (the product of all moduli)

  2. For each i, compute Mᵢ = M/mᵢ (the product of all moduli except mᵢ)

  3. For each i, find yᵢ, the modular inverse of Mᵢ modulo mᵢ (solve Mᵢ · yᵢ ≡ 1 (mod mᵢ) using methods you already know)

  4. Construct the solution: x ≡ a₁M₁y₁ + a₂M₂y₂ + ... + aₖMₖyₖ (mod M)

Think of it like assembling puzzle pieces: each term aᵢMᵢyᵢ is designed to be ≡ aᵢ (mod mᵢ) but ≡ 0 (mod mⱼ) for all j ≠ i. When you add them all together, each congruence condition is satisfied independently!

Key Takeaway: The CRT Construction Algorithm builds the solution by creating weighted terms (aᵢMᵢyᵢ) that satisfy one congruence while being invisible to the others, then summing these terms modulo the product of all moduli.