Multiplicative inverse modulo m

[arfla]

Hello, I am doing coursework on Maths at the moment about RSA encryption, and I am kind of stuck with one of my calculations. I want to calculate the following 67 D = 1 (mod 15120), I know the result which is D = 14443, but I need to understand the process behind it as I need to explain it. Could someone please help me, it's really urgent! It doesn't need to be this exact example, just the same formula so I understand the maths behind it. I have been trying to find a website which explains it. However, I wasn't able to find one which makes it clear and understandable.
Thanks in advance!

 

[HallsofIvy]

67D= 1 (mod 15120) is the same as 67D= 15120i+ 1 for some integer I. Rewrite that as the "Diophantine equation" 67D- 15120i= 1. 67 divides into 15120 225 times with remainder 45: 15120- (225)(67)= 45. 45 divides into 67 once with remainder 22: 67- 45= 22. 22 divides into 45 twice with remainder 1: 45- 2(22)= 1. Replace that 22 with 67- 45: 45- 2(67- 45)= 3(45)- 2(67)= 1. replace that 45 with 15120- 225(67): 3(15120- 225(67))- 2(67)= 3(15120)- 677(67)= 67(-677)- (15120)(-3)= 1. So one solution to 67D- 15120i= 1 is D= -677 and i= -3.
Check: 67(-677)- 15120(-3)= 1.

But it is easy to see that D= -677+ 15120k, i= -3+67k is also a solution: 67(-677+ 15120k)- 15120(-3+ 67k)= 67(-677)- 15120(-3)+ 67(15120k)- 15120(67k)= 1.

Taking k= 1 gives the lowest positive solution D= -677+ 15120= 14443.

 

[arfla]

67D= 1 (mod 15120) is the same as 67D= 15120i+ 1 for some integer I. Rewrite that as the "Diophantine equation" 67D- 15120i= 1. 67 divides into 15120 225 times with remainder 45: 15120- (225)(67)= 45. 45 divides into 67 once with remainder 22: 67- 45= 22. 22 divides into 45 twice with remainder 1: 45- 2(22)= 1. Replace that 22 with 67- 45: 45- 2(67- 45)= 3(45)- 2(67)= 1. replace that 45 with 15120- 225(67): 3(15120- 225(67))- 2(67)= 3(15120)- 677(67)= 67(-677)- (15120)(-3)= 1. So one solution to 67D- 15120i= 1 is D= -677 and i= -3.
Check: 67(-677)- 15120(-3)= 1.

But it is easy to see that D= -677+ 15120k, i= -3+67k is also a solution: 67(-677+ 15120k)- 15120(-3+ 67k)= 67(-677)- 15120(-3)+ 67(15120k)- 15120(67k)= 1.

Taking k= 1 gives the lowest positive solution D= -677+ 15120= 14443.

That is perfectly explained, thank you so much!