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

The CRT with three moduli

#CRT#three moduli#pairwise coprime

Statement

Solve
{x≡1(mod3)x≡2(mod5)x≡3(mod7)\begin{cases}x\equiv1\pmod3\\ x\equiv2\pmod5\\ x\equiv3\pmod7\end{cases}

Hint

Combine two congruences first, then the third.

Show solutionHide solution

Solution

First two. From the first two: x≡7(mod15)x\equiv7\pmod{15} (verify: 7≡1(mod3)7\equiv1\pmod3, 7≡2(mod5)7\equiv2\pmod5).

Combine with third. x=7+15kx=7+15k, need 7+15k≡3(mod7)7+15k\equiv3\pmod7. 15≡1(mod7)15\equiv1\pmod7, 7≡0(mod7)7\equiv0\pmod7, so 15k≡3(mod7)15k\equiv3\pmod7, i.e. k≡3(mod7)k\equiv3\pmod7.

Solution. x=7+15(3+7m)=52+105mx=7+15(3+7m)=52+105m.

Conclusion. x≡52(mod105)x\equiv52\pmod{105}.

Check. 52≡1(mod3)52\equiv1\pmod3, 52≡2(mod5)52\equiv2\pmod5, 52≡3(mod7)52\equiv3\pmod7. Correct.