Lesson 074
Chinese Remainder Theorem
Combine Modular Congruences
1:00How to find a number that satisfies multiple remainder conditions simultaneously, and why the solution is unique when the moduli are pairwise coprime.
By the end, you can
- State the CRT hypothesis (pairwise coprime moduli) and explain why it is necessary.
- Distinguish "pairwise coprime" from "prime" and give an example of coprime-but-composite moduli.
- Compute N, cofactors Nᵢ, and modular inverses for a given system of congruences.
- Apply the full CRT algorithm to find the unique solution modulo N.
- Verify a proposed solution by checking each congruence.
- Explain why two solutions must differ by a multiple of N, establishing uniqueness.
- Describe the gcd condition for non-coprime moduli and state that uniqueness is then mod lcm.
- Identify at least two real-world algorithms that rely on CRT.
Up next in Math, Memory & Files
