if 13* D = 1 mod 60 then D = 37 how?

Question

I am solving an example problem, RSA algorithm
I have been given two prime numbers 7 and 11. Let's say p=7 and q=11
I have to calculate the decryption key, d, for some encryption key, e.

Firstly I calculated n=p*q which implies that n=77.

Suppose that e=13,
to calculate d I used the formula d*e = 1 mod fi, where fi=(p-1)(q-1), and so fi=60

The final equation becomes 13*d = 1 mod fi

According to some solved example d is calculated to be 37, how is this result obtained?

Any help would be appreciated.

Answer 1

i think this is what you are looking for

Verifying the answer is easy, finding it in the first place, a little more work.

Verification:

13 * 37 = 481 
481 = 8 * 60 + 1

Hence if you divide 13 * 37 by 60 you have remainder 1.

Alternate answers:

Any integer of the form (37 + 60 k) where k is any integer is also a solution. (97, -23, etc.)

To find the solution you can proceed as follows:
Solve:

13 d = 1 + 60 k 
mod 13:
0 = 1 + 8k (mod 13) 
8k = -1 (mod 13) 
Add 13's until a multiple of 8 is found: 
8k = 12 or 25 or 38 or 51 or 64 .... aha a multiple of 8! 
k = 64 / 8 = 8 
Substitute k = 8 back into 13 d = 1 + 60 k 
13 d = 1 + 8 * 60 = 481 
481 /13 = 37 

and that is the answer.

Answer 2

Use the extended Euclidean algorithm to compute integers x and y such that

13*x+60*y=1

Then x is the answer you're looking for, mod 60.