Non-Coprime Congruences and the Wrong Modulus
In a number-theory warm-up, students solve the system x≡5 (mod 6), x≡8 (mod 9). A candidate notices gcd(6,9)=3, and since 5≡8≡2 (mod 3), they decide the system is consistent. They then multiply the moduli and claim the solution is unique modulo 54, writing x≡17 (mod 54). Substituting x=17 checks in both congruences, so they conclude that all solutions are 17+54k. The answer key gives a smaller modulus, and the candidate is confused when a classmate shows that x=35 also satisfies both congruences. No computational error occurred in checking 17; the issue is structural. The teacher asks the class to find the complete solution set, explain why 35 belongs, and identify the incorrect use of the Chinese remainder theorem.
1. Find the complete solution set and the smallest positive solution.
Read the worked answer
Write x=5+6k. The second congruence gives 5+6k≡8 (mod 9), so 6k≡3 (mod 9). Dividing the congruence by 3 gives 2k≡1 (mod 3), hence k≡2 (mod 3). Thus k=2+3t and x=5+6(2+3t)=17+18t. The complete solution set is x≡17 (mod 18). The smallest positive solution is 17; the next is 35, which checks as 35 mod 6=5 and 35 mod 9=8.
2. Explain the error in using modulus 54 and why 35 is a solution.
Read the worked answer
The Chinese remainder theorem guarantees uniqueness modulo the product of the moduli only when the moduli are coprime. Here gcd(6,9)=3, so the combined modulus is lcm(6,9)=18, not 54. The congruence x≡17 (mod 54) is only one residue class inside the full class x≡17 (mod 18); it omits 17+18=35, 17+36=53, and so on. The system is consistent because 5−8=−3 is divisible by gcd(6,9)=3. Once consistent, there is one class modulo 18. Checking x=17 only verifies a representative, not the modulus; 35≡17 (mod 18) but not mod 54, so it satisfies the same two original congruences.