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

A system of congruences

#system#CRT#linear congruences

Statement

Solve x≡5(mod8)x\equiv5\pmod{8}, x≡3(mod9)x\equiv3\pmod{9}, x≡4(mod7)x\equiv4\pmod{7}.

Hint

Apply CRT successively.

Show solutionHide solution

Solution

First two. x≡5(mod8)x\equiv5\pmod8, x≡3(mod9)x\equiv3\pmod9. Try x=5+8kx=5+8k: 5+8k≡3(mod9)5+8k\equiv3\pmod9, 8k≡−2≡7(mod9)8k\equiv-2\equiv7\pmod9. 8−1≡8(mod9)8^{-1}\equiv8\pmod9 (since 8⋅8=64≡18\cdot8=64\equiv1), so k≡7⋅8=56≡2(mod9)k\equiv7\cdot8=56\equiv2\pmod9. x=5+8(2+9m)=21+72mx=5+8(2+9m)=21+72m.

Combine with third. 21+72m≡4(mod7)21+72m\equiv4\pmod7. 21≡021\equiv0, 72≡2(mod7)72\equiv2\pmod7, so 2m≡4(mod7)2m\equiv4\pmod7, m≡2(mod7)m\equiv2\pmod7. x=21+72(2+7n)=165+504nx=21+72(2+7n)=165+504n.

Conclusion. x≡165(mod504)x\equiv165\pmod{504}.

Check. 165≡5(mod8)165\equiv5\pmod8, 165≡3(mod9)165\equiv3\pmod9, 165≡4(mod7)165\equiv4\pmod7. Correct.