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

A system of linear congruences

#system#linear congruences#CRT

Statement

Solve
{2x≡3(mod5)3x≡4(mod7)\begin{cases}2x\equiv3\pmod5\\ 3x\equiv4\pmod7\end{cases}

Hint

Solve each congruence first, then combine with CRT.

Show solutionHide solution

Solution

First. 2−1≡3(mod5)2^{-1}\equiv3\pmod5, so x≡9≡4(mod5)x\equiv9\equiv4\pmod5.

Second. 3−1≡5(mod7)3^{-1}\equiv5\pmod7, so x≡20≡6(mod7)x\equiv20\equiv6\pmod7.

CRT. x≡4(mod5)x\equiv4\pmod5, x≡6(mod7)x\equiv6\pmod7. Solve: x=4+5kx=4+5k, 4+5k≡6(mod7)4+5k\equiv6\pmod7, 5k≡2(mod7)5k\equiv2\pmod7, k≡10≡3(mod7)k\equiv10\equiv3\pmod7. So x=4+5(3+7m)=19+35mx=4+5(3+7m)=19+35m.

Conclusion. x≡19(mod35)x\equiv19\pmod{35}.