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

Existence and Uniqueness in CRT

Explore why CRT solutions exist and are unique modulo the product of the moduli when conditions are met.

Existence and Uniqueness in CRT

You'll learn: Why the Chinese Remainder Theorem guarantees exactly one solution modulo the product of the moduli when they are pairwise coprime.

The Core Guarantee

The Chinese Remainder Theorem doesn't just tell you that solutions to systems of congruences might exist—it guarantees both that a solution exists and that it's essentially unique, provided the moduli are pairwise relatively prime.

When you have a system like:

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

where gcd(nᵢ, nⱼ) = 1 for all i ≠ j, CRT promises:

Existence

There is always at least one solution x that simultaneously satisfies all congruences. This works because the pairwise coprimality allows us to "piece together" solutions using the construction method (involving products N/nᵢ and their inverses).

Uniqueness Modulo N

Any two solutions x₁ and x₂ differ by a multiple of N = n₁·n₂·...·nₖ. In other words, the solution is unique modulo N. If x₀ is one solution, every solution has the form x₀ + kN for integer k.

Why Uniqueness Matters

Think of it like a combination lock with independent dials: if the dials (moduli) don't interfere with each other (coprime condition), there's exactly one position (solution) within a full rotation cycle (modulo N) that satisfies all settings.

Without pairwise coprimality, solutions might not exist at all, or you might have multiple distinct solutions within the same range—the structure breaks down.

Key Takeaway: When moduli are pairwise coprime, CRT guarantees exactly one solution modulo their product—no more, no less—making it a powerful tool for solving modular systems deterministically.