Maths WorkshopMaths problems with full solutions
Exercise 924Number theory › Divisibility and gcdL1Added 3 Nov 2026

Finding modular inverses

#modular inverse#Bézout#congruences

Statement

Find the inverse of 77 modulo 1111.

Hint

Find uu with 7u≡1(mod11)7u\equiv1\pmod{11} using Bézout or trial.

Show solutionHide solution

Solution

Trial. 7⋅2=14≡37\cdot2=14\equiv3, 7⋅3=21≡107\cdot3=21\equiv10, 7⋅4=28≡67\cdot4=28\equiv6, 7⋅5=35≡27\cdot5=35\equiv2, 7⋅8=56≡17\cdot8=56\equiv1. So 7−1≡8(mod11)7^{-1}\equiv8\pmod{11}.

Bézout. gcd⁡(7,11)=1\gcd(7,11)=1: 11=1⋅7+411=1\cdot7+4, 7=1⋅4+37=1\cdot4+3, 4=1⋅3+14=1\cdot3+1, so 1=4−3=4−(7−4)=2⋅4−7=2(11−7)−7=2⋅11−3⋅71=4-3=4-(7-4)=2\cdot4-7=2(11-7)-7=2\cdot11-3\cdot7. So 7⋅(−3)≡1(mod11)7\cdot(-3)\equiv1\pmod{11}, i.e. 7−1≡−3≡8(mod11)7^{-1}\equiv-3\equiv8\pmod{11}.

Conclusion. 7−1≡8(mod11)7^{-1}\equiv8\pmod{11}.