I need to find 55^-1 Mod (89)
So what I did was use the extended Euclidean algorithm:
89 = 55(1) + 34
55 = 34(1) + 21
34 = 21(1) + 13
21 = 13(1) + 8
13 = 8(1) + 5
8 = 5(1) + 3
5 = 3(1) + 2
3 = 2(1) + 1
Then I worked backwards:
1 = 3 - 2(1)
= 3 - [5 - 3(1)](1)
= 3(2) - 5(1)
= [8 - 5(1)](2) - 5(1)
= 8(2) - 5(3)
= 8(2) - [13 - 8(1)](3)
= 8(4) - 13(3)
= [21 - 13(1)](4) - 13(3)
= 21(4) - 13(5)
= 21(6) - 34(5)
= [55 - 34(1)](6) - 34(5)
= 55(6) - 34(7)
= 55(6) - [89 - 55(1)](7)
= 55(8) - 89(7)
So what that tells me is that 8 is the multiplicative inverse of 55 and -7 is the multiplicative inverse of 89. However, I'm suppose to be getting 34 (checked here: http://webscript.princeton.edu/~dsri/modular-inversion-answer.php?n=55&p=89).
So what am I doing wrong? Also, how would I tackle a problem with a huge number like 17^-1 mod (2^32)?
So what I did was use the extended Euclidean algorithm:
89 = 55(1) + 34
55 = 34(1) + 21
34 = 21(1) + 13
21 = 13(1) + 8
13 = 8(1) + 5
8 = 5(1) + 3
5 = 3(1) + 2
3 = 2(1) + 1
Then I worked backwards:
1 = 3 - 2(1)
= 3 - [5 - 3(1)](1)
= 3(2) - 5(1)
= [8 - 5(1)](2) - 5(1)
= 8(2) - 5(3)
= 8(2) - [13 - 8(1)](3)
= 8(4) - 13(3)
= [21 - 13(1)](4) - 13(3)
= 21(4) - 13(5)
= 21(6) - 34(5)
= [55 - 34(1)](6) - 34(5)
= 55(6) - 34(7)
= 55(6) - [89 - 55(1)](7)
= 55(8) - 89(7)
So what that tells me is that 8 is the multiplicative inverse of 55 and -7 is the multiplicative inverse of 89. However, I'm suppose to be getting 34 (checked here: http://webscript.princeton.edu/~dsri/modular-inversion-answer.php?n=55&p=89).
So what am I doing wrong? Also, how would I tackle a problem with a huge number like 17^-1 mod (2^32)?
Last edited:
