Exercise 849Number theory › CongruencesL1Added 3 Nov 2026

Finding modular inverses

#modular inverse#extended Euclidean#algorithm

Statement

Find $17^{-1}\pmod{43}$ .

Hint

Use the extended Euclidean algorithm.

Show solutionHide solution

Euclidean. $43=2\cdot17+9$ , $17=1\cdot9+8$ , $9=1\cdot8+1$ .

Back. $1=9-8=9-(17-9)=2\cdot9-17=2(43-2\cdot17)-17=2\cdot43-5\cdot17$ .

Inverse. $17\cdot(-5)\equiv1\pmod{43}$ , so $17^{-1}\equiv-5\equiv38\pmod{43}$ .

Check. $17\cdot38=646=15\cdot43+1$ . Correct.

Conclusion. $17^{-1}\equiv38\pmod{43}$ .