Maths WorkshopMaths problems with full solutions
Exercise 1578Number theory › CongruencesL1Added 3 Nov 2026

CRT with non-coprime moduli

#CRT#non-coprime#compatibility

Statement

Solve
{x≡4(mod6)x≡7(mod9)\begin{cases}x\equiv4\pmod6\\ x\equiv7\pmod9\end{cases}

Hint

The system is solvable iff a≡b(modgcd⁡(m,n))a\equiv b\pmod{\gcd(m,n)}.

Show solutionHide solution

Solution

Compatibility. gcd⁡(6,9)=3\gcd(6,9)=3. Need 4≡7(mod3)4\equiv7\pmod3: 4−7=−3≡0(mod3)4-7=-3\equiv0\pmod3. Compatible.

Solve. From the first, x=4+6kx=4+6k. Substitute: 4+6k≡7(mod9)4+6k\equiv7\pmod9, so 6k≡3(mod9)6k\equiv3\pmod9. Divide by 33: 2k≡1(mod3)2k\equiv1\pmod3, so k≡2(mod3)k\equiv2\pmod3, k=2+3mk=2+3m. Then x=4+6(2+3m)=16+18mx=4+6(2+3m)=16+18m.

Conclusion. x≡16(mod18)x\equiv16\pmod{18}.

Check. 16≡4(mod6)16\equiv4\pmod6, 16≡7(mod9)16\equiv7\pmod9. Correct.