Exercise 924Number theory › Divisibility and gcdL1Added 3 Nov 2026 Finding modular inverses #modular inverse#Bézout#congruences StatementFind the inverse of 777 modulo 111111. HintFind uuu with 7u≡1(mod11)7u\equiv1\pmod{11}7u≡1(mod11) using Bézout or trial. Show solutionHide solutionSolutionTrial. 7⋅2=14≡37\cdot2=14\equiv37⋅2=14≡3, 7⋅3=21≡107\cdot3=21\equiv107⋅3=21≡10, 7⋅4=28≡67\cdot4=28\equiv67⋅4=28≡6, 7⋅5=35≡27\cdot5=35\equiv27⋅5=35≡2, 7⋅8=56≡17\cdot8=56\equiv17⋅8=56≡1. So 7−1≡8(mod11)7^{-1}\equiv8\pmod{11}7−1≡8(mod11).Bézout. gcd(7,11)=1\gcd(7,11)=1gcd(7,11)=1: 11=1⋅7+411=1\cdot7+411=1⋅7+4, 7=1⋅4+37=1\cdot4+37=1⋅4+3, 4=1⋅3+14=1\cdot3+14=1⋅3+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\cdot71=4−3=4−(7−4)=2⋅4−7=2(11−7)−7=2⋅11−3⋅7. So 7⋅(−3)≡1(mod11)7\cdot(-3)\equiv1\pmod{11}7⋅(−3)≡1(mod11), i.e. 7−1≡−3≡8(mod11)7^{-1}\equiv-3\equiv8\pmod{11}7−1≡−3≡8(mod11).Conclusion. 7−1≡8(mod11)7^{-1}\equiv8\pmod{11}7−1≡8(mod11).