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

Applications of the modular inverse

#modular inverse#application#linear congruence

Statement

Solve the linear congruence 23x≡17(mod31)23x\equiv17\pmod{31}.

Hint

Find 23−1(mod31)23^{-1}\pmod{31}.

Show solutionHide solution

Solution

Euclidean. 31=1⋅23+831=1\cdot23+8, 23=2⋅8+723=2\cdot8+7, 8=1⋅7+18=1\cdot7+1.

Back. 1=8−7=8−(23−2⋅8)=3⋅8−23=3(31−23)−23=3⋅31−4⋅231=8-7=8-(23-2\cdot8)=3\cdot8-23=3(31-23)-23=3\cdot31-4\cdot23.

Inverse. 23−1≡−4≡27(mod31)23^{-1}\equiv-4\equiv27\pmod{31}.

Solution. x≡27⋅17=459x\equiv27\cdot17=459. 459=14⋅31+25459=14\cdot31+25, so x≡25(mod31)x\equiv25\pmod{31}.

Check. 23⋅25=575=18⋅31+1723\cdot25=575=18\cdot31+17. Correct.

Conclusion. x≡25(mod31)x\equiv25\pmod{31}.