I m looking an easy way to compute inverse modulo of some numbers. I had this example(made from RSA computation) pick p = 7 and q =11 i calculate the $\phi$ = 60 and n= p*q = 77.
I chose an e = 7 I need to find the inverse multiplicative in this way
$7^{-1} $mod 60
I used this type of simple computation
60 = 8 (7) +4
7= 1(4) +3
4 = 1(3) +1
after computing the inverse
1= 4- 1(3)
= 4 - 1(7 -1(4))
= 2(4) - 1(7)
= 2(60 -8(7)) -1(7)
= 2(60) -17(7)
and 2(60) mod 60 = 0
so I have just -17(7) that should be an inverse modulo of 7 mod 60, but something didn't work.
If I use 11 for calculating the inverse of 11mod 60 in the same way
60= 5(11)+5
11 = 2(5) +1
so
1= 11-2(5)
= 11 -2(60-5(11))
= 11(11) -2(60)
and in this case, 11 is right, is the inverse of 11mod 60.
I didn't understand why I m wronging in the first case. Someone can clarify to me why happened this?
I know that I should use different method of calculating inverse, but I need to compute in fast and easy way this stuff, I m not a very mathematic expert.