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

A CRT application

#CRT#application#calendar

Statement

Find the smallest positive integer that leaves remainder 22 when divided by 33, remainder 33 when divided by 55, and remainder 22 when divided by 77.

Hint

Solve the system by CRT.

Show solutionHide solution

Solution

System. x≡2(mod3)x\equiv2\pmod3, x≡3(mod5)x\equiv3\pmod5, x≡2(mod7)x\equiv2\pmod7.

First two. x≡8(mod15)x\equiv8\pmod{15} (from 8≡2(mod3)8\equiv2\pmod3, 8≡3(mod5)8\equiv3\pmod5).

Combine with third. 8+15k≡2(mod7)8+15k\equiv2\pmod7, so 1+k≡2(mod7)1+k\equiv2\pmod7 (since 8≡18\equiv1 and 15≡115\equiv1), k≡1(mod7)k\equiv1\pmod7. Thus x=8+15=23x=8+15=23.

Conclusion. x=23x=23 is the smallest positive solution.

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