Questions: Simultaneous Congruences and Chinese Remainder Theorem

Question 1

You want to apply CRT to the system: x ≡ 1 (mod 4) and x ≡ 1 (mod 6). Is CRT applicable, and why?

• A. Yes — the moduli are small integers, so CRT always applies in this range
• B. No — CRT requires the moduli to be pairwise coprime, and gcd(4, 6) = 2 ≠ 1
• C. Yes — CRT applies to any system of linear congruences regardless of moduli
• D. No — CRT only applies when there are three or more congruences in the system

Answer: (B)

CRT requires pairwise coprime moduli — every pair must have gcd equal to 1. Here gcd(4, 6) = 2, so the coprimality condition fails. When moduli share a common factor, the system may have no solution or infinitely many solutions in an uncontrolled way. CRT does not apply and uniqueness is not guaranteed. The size of the moduli and the number of congruences are irrelevant to this requirement.

Question 2

When the conditions of CRT are satisfied, what does the theorem guarantee about the solution?

• A. At least one solution exists, but uniqueness depends on the specific remainders
• B. Exactly one solution exists modulo the product of all the moduli
• C. The solution can always be found without computing any modular inverses
• D. The smallest positive solution is guaranteed to be less than the largest modulus

Answer: (B)

CRT's guarantee is precise and strong: when the moduli are pairwise coprime, the system has exactly one solution modulo M = m₁m₂⋯mₖ. The solution space is not just nonempty — it is exactly one residue class within the range [0, M). This is what makes CRT a decomposition theorem: the solution is unique within a predictable structure. The constructive proof provides an algorithm using modular inverses (option C is false — modular inverses are essential to the algorithm).

Question 3

If two moduli share a common factor, the Chinese Remainder Theorem still guarantees a unique solution, just within a smaller modulus.

• T. True
• F. False

Answer: False

CRT's uniqueness guarantee depends entirely on the pairwise coprime condition. When moduli share a factor, the system may be inconsistent (no solution) or it may have infinitely many solutions that are not controlled by the product M. For example, x ≡ 1 (mod 4) and x ≡ 3 (mod 6) has no solution because the two conditions conflict modulo 2. The pairwise coprime condition is not merely convenient — it is what makes the theorem work.

Question 4

CRT can be interpreted as saying that arithmetic modulo M (where M is a product of pairwise coprime factors) decomposes into independent arithmetic modulo each factor, with solutions reassembled afterward.

• T. True
• F. False

Answer: True

This decomposition interpretation is the deepest insight of CRT. Computing modulo M is exactly equivalent to computing modulo each mᵢ simultaneously and then reassembling. This is why CRT is foundational in cryptography — large modular multiplications can be replaced by several smaller independent computations done in parallel. The theorem guarantees not just that a solution exists, but that this decomposition is exact and invertible.

Question 5

Why is the pairwise coprime condition essential for the Chinese Remainder Theorem, and what can go wrong when two moduli share a common factor?

Model answer: The pairwise coprime condition ensures that the modular inverse of Mᵢ = M/mᵢ modulo mᵢ exists for each i — this inverse is the key ingredient in the constructive algorithm. More fundamentally, coprimality prevents conflicts: if mᵢ and mⱼ share a factor d, then both congruences place constraints modulo d, and those constraints may be contradictory. For example, x ≡ 0 (mod 4) and x ≡ 1 (mod 6) conflict because modulo 2 the first requires x even and the second requires x odd. When moduli are coprime, no such conflicts can arise because no two moduli share any prime factor.

The pairwise coprime condition is not a technicality — it is what transforms a potentially inconsistent system of constraints into one guaranteed to have a unique solution. The uniqueness (mod M) is also essential: it means the solution space has exactly the predictable size M, enabling the decomposition interpretation that makes CRT useful in cryptographic algorithms.