Multiplicative Inverse

It can be done by using Euclidean Algorithm :

Example 1:
Find multiplicative inverse of 3 mod 26.
so let e = 3,n = 26, e^{-1} = ?


formula: gcd(e, n) , gcd(3, 26)


steps:always put bigger number at left, then only start to divide and
fill up numbers and remainder
26 = (3)
(1) 26 = 8(3) + 2
.......always take down bracket and remainder
3 = (2)
(2) 3 = 1(2) + 1
2 = 2(1) ......stop bec remainder is 0


Extended Euclidean Algorithm : to reverse it
(2)...... 3 = 1(2) + 1
........always let the equation to be 1 = ab - c , let 1 to be left
1 = 3 - 1(2)
........always replace the figure in bracket that smallest
with something, as u noted there will always is the remainder
in above calucation,
2 in (1).....26 = 8(3) + 2,
so 2 = 26 - 8(3)
1 = 3 - 1 [26 - 8(3)]
.......dont break the small bracket whenever we expand
1 = 3 - 1(26) + 8(3)
......find the common number in bracket and sum up
1 = 1(3) + 8(3) - 1(26)
1 = 9(3) - 1(26)


so, we can see 9(3), the multiplicative invers of 3 =9 mod 26,
3^{-1} = 9 mod 26


Example 2:
Find multiplicative inverse of 5 mod 26.
so let e = 5,n = 26, e^{-1} = ?


Euclidean Algorithm :
(1) 26 = 5(5) + 1
5 = 5(1)
Extended Euclidean Algorithm :
(1) 1 = 26 - 5(5)


so 5^{-1} congruent (-5) mod 26,
26 - 5 = 12
so 5^{-1} congruent 12 mod 26, ans is 12


Example 3:
Find multiplicative inverse of 1261 mod 18648.
so let e = 1261,n = 18648, e^{-1} = ?


Euclidean Algorithm :
(1) 18648 = 14(1261) + 994
(2) 1261 = 1(994) + 267
(3) 994 = 3(267) + 193
(4) 267 = 1(193) + 74
(5) 193 = 2(74) + 45
(6) 74 = 1(45) + 29
(7) 45 = 1(29) + 16
(8) 29 = 1(16) + 13
(9) 16 = 1(13) + 3
(10) 13 = 4(3) + 1
3 = 3(1)


Extended Euclidean Algorithm :
(10) 1 = 13 - 4(3)
(9) 1 = 13- 4[16-1(13)]
1 = 13- 4(16)+4(13)
1 = 5(13)- 4(16)
(8) 1 = 5[29-1(16)]- 4(16)
1 = 5(29)-5(16)- 4(16)
1 = 5(29)-9(16)
(7) 1 = 5(29)-9[45-1(29)]
1 = 5(29)-9(45)+9(29)
1 = 14(29)-9(45)
(6) 1 = 14(29)-9(45)
1 = 14[74-1(45)]-9(45)
1 = 14(74)-14(45)-9(45)
1 = 14(74)-23(45)
(5) 1 = 14(74)-23[193 - 2(74)]
1 = 14(74)-23(193) + 46(74)
1 = 60(74)-23(193)
(4) 1 = 60[267-1(193)]-23(193)
1 = 60(267)-60(193)-23(193)
1 = 60(267)-83(193)
(3) 1 = 60(267)-83[994-3(267)]
1 = 60(267)-83(994)+249(267)
1 = 309(267)-83(994)
(2) 1 = 309[1261 - 1(994)]-83(994)
1 = 309(1261) - 309(994)-83(994)
1 = 309(1261) - 392(994)
(1) 1 = 309(1261) - 392[18648 - 14(1261)]
1 = 309(1261) - 392(18648) + 5488(1261)
1 = 5795(1261) - 392(18648)

so 1261^{-1} congruent (5795) mod 18648, ans is 5795