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

The Chinese remainder theorem (two moduli)

#Chinese remainder theorem#CRT#coprime moduli

Statement

Solve
{x≡2(mod5)x≡3(mod7)\begin{cases}x\equiv2\pmod{5}\\ x\equiv3\pmod{7}\end{cases}

Hint

Write x=2+5kx=2+5k and substitute into the second congruence.

Show solutionHide solution

Solution

Substitute. 2+5k≡3(mod7)2+5k\equiv3\pmod7, so 5k≡1(mod7)5k\equiv1\pmod7.

Inverse. 5−1≡3(mod7)5^{-1}\equiv3\pmod7 (since 5⋅3=15≡15\cdot3=15\equiv1). So k≡3(mod7)k\equiv3\pmod7, i.e. k=3+7mk=3+7m.

Solution. x=2+5(3+7m)=17+35mx=2+5(3+7m)=17+35m.

Conclusion. x≡17(mod35)x\equiv17\pmod{35}.