Questions: The Chinese Remainder Theorem and Its Applications

Question 1

You want to solve the system x ≡ 3 (mod 4) and x ≡ 1 (mod 6). Can the Chinese Remainder Theorem be directly applied?

• A. Yes — there are two congruences and two unknowns, so CRT applies
• B. No — 4 and 6 share a common factor of 2, so the moduli are not pairwise coprime and CRT's uniqueness guarantee fails
• C. Yes — CRT applies to any system of linear congruences regardless of the moduli
• D. No — CRT only works when all moduli are prime numbers

Answer: (B)

CRT requires pairwise coprime moduli. Since gcd(4, 6) = 2, these moduli share a factor — they are not coprime. When moduli share a factor, the remainders become dependent: not every combination of remainders is achievable, and when solutions do exist, they may not be unique modulo 4×6=24. The theorem's guarantee breaks down. Option A ignores the coprimality condition. Option C is simply false. Option D is too restrictive — CRT works for any pairwise coprime integers, not only primes.

Question 2

Why does CRT require moduli to be pairwise coprime? What goes wrong if two moduli share a common factor?

• A. Shared factors make the arithmetic harder to compute, but solutions still always exist
• B. Shared factors mean the total modulus N = n₁n₂⋯nₖ would be too large for practical computation
• C. Shared factors create dependencies between remainders — not every combination is achievable, so the bijection between remainder tuples and residues mod N breaks down
• D. Shared factors only matter when the moduli are larger than 100

Answer: (C)

The heart of CRT is that coprime moduli are independent: knowing x mod n₁ tells you nothing about x mod n₂ when gcd(n₁, n₂) = 1. Independence means every combination of remainders (a₁, a₂, …, aₖ) is achievable, giving a perfect bijection — like a coordinate system where every coordinate tuple names exactly one point. When two moduli share a factor, their remainders constrain each other: if n₁ = 4 and n₂ = 6, then x mod 2 is determined by both, so not all (a₁, a₂) pairs are simultaneously satisfiable.

Question 3

For pairwise coprime moduli n₁, n₂, …, nₖ with N = n₁n₂⋯nₖ, every tuple of remainders (a₁, a₂, …, aₖ) corresponds to exactly one value of x in the range [0, N).

• T. True
• F. False

Answer: True

This is the coordinate-system interpretation of CRT and is exactly what it guarantees. Pairwise coprimality makes the remainders fully independent, so every combination is achievable (existence) and achievable in only one way modulo N (uniqueness). The set of integers mod N is in bijection with the Cartesian product of integers mod n₁, mod n₂, …, mod nₖ. This is the reason CRT is so powerful: it transforms a single problem modulo a large N into independent problems modulo smaller, simpler moduli.

Question 4

If x₀ is a solution to a CRT system with moduli n₁, n₂, …, nₖ and N = n₁n₂⋯nₖ, then x₀ + N is also a valid solution.

• T. True
• F. False

Answer: True

CRT guarantees a solution that is unique modulo N, meaning the full solution set is {x₀, x₀ + N, x₀ + 2N, …} — infinitely many integers, all differing by multiples of N. Adding N to x₀ doesn't change its remainder mod any nᵢ (since N is divisible by each nᵢ), so x₀ + N satisfies all the same congruences. This is why we say the solution is 'unique modulo N' rather than 'there is exactly one solution.'

Question 5

Explain why the pairwise coprimality requirement is essential to CRT. What goes wrong if two moduli share a common factor?

Model answer: Pairwise coprimality ensures that the moduli are independent — knowing a number's remainder mod nᵢ gives no information about its remainder mod nⱼ when gcd(nᵢ, nⱼ) = 1. This independence means every combination of remainders is achievable. If two moduli share a common factor d > 1, their remainders become coupled: since x mod d is determined by both congruences, not every pair (aᵢ, aⱼ) is simultaneously satisfiable. For example, x ≡ 1 (mod 4) and x ≡ 0 (mod 6) has no solution because x ≡ 1 (mod 4) implies x is odd, but x ≡ 0 (mod 6) implies x is even.

The independence of coprime moduli is the theorem's engine. When moduli are coprime in pairs, the remainders behave like independent coordinates, and the map from x to its remainder tuple is a bijection onto the product of residue classes. Shared factors destroy this independence, introducing constraints among the remainders that prevent certain combinations from being realized.