Get integer solutions for $13x\equiv1\pmod{60}$ by euclidean method I am now studying the RSA algorithm.
The keypair generation equation of RSA is $d*e = 1 \pmod{(n-1)(q-1)}$
(where d, e is public key private key each other)
In this situation I got the private key$= 13, n=7, q=11$
so the keypair generation equation will be $13d \equiv 1 \pmod{60}$...
therefore, $13 = 60n + 1$
and I found the $n=8$ by using Euclidean method, $60 = 13 \cdot 4 + 8..$
so the $d$ will be $37$...
Is this the correct way?  (using Euclidean method)...
 A: You're solving $13x\equiv 1\pmod{60}$, i.e. you're searching for the Modular Multiplicative Inverse of $13$ mod $60$, i.e. you're searching for $13^{-1}\bmod 60$, which exists because $\gcd(13,60)=1$.
More generally, $a^{-1}\bmod b$ exists if and only if $\gcd(a,b)=1$. See Bézout's Lemma: there always exist $s,t\in\mathbb Z$ such that $as+bt=\gcd(a,b)$, and you can find these $s,t$ using the Extended Euclidean Algorithm (EEA).
Here's one way you can apply EEA: subtract consecutive equations:
$$60=60(1)+13(0)\\13=60(0)+13(1)\\8=60(1)+13(-4)\\5=60(-1)+13(5)\\3=60(2)+13(-9)\\2=60(-3)+13(14)\\1=60(5)+13(-23)$$
Therefore $13(-23)\equiv 1\pmod{60}$, so $13(-23)\equiv 13x\pmod{60}$. Since $\gcd(13,60)=1$, by Euclid's Lemma this is equivalent to $-23\equiv x\pmod{60}$, i.e. $x\equiv 37\pmod{60}$.
A: Through continued fractions (it is an efficient way to encode Euclid's algorithm) we have:
$$ \frac{60}{13}=[4;1,1,1,1,2] \tag{1}$$
and:
$$ [4;1,1,1,1]=\frac{23}{5} \tag{2}$$
and the difference of such numbers is $\pm\frac{1}{5\cdot 13}$ by a general property of continued fractions. 
In our case:
$$ \frac{60}{13}-\frac{23}{5} = \frac{1}{65}\tag{3} $$
from which we get:
$$ 60\cdot 5 - 23\cdot 13 = 1 \tag{4}$$
as well as:
$$ 13\cdot (-23)\equiv 1\pmod{60} \tag{5}$$
so the inverse of $13$ in $\mathbb{Z}/(60\mathbb{Z})^*$ is $-23=\color{red}{37}$ as you claimed.
A: How I would apply the Euclidean algorithm to solve 13x+ 60y= 1 (from 13x= 1 (mod 60):  13 divides into 60 4 times with remainder 8: 60- 4(13)= 8.  8 divides into 13 once with remainder 5: 13- 8= 5. 5 divides into 8 once with remainder 3: 8- 5= 3.  3 divides into 5 once with remainder 2: 5- 3= 2.  2 divides into 3 once with remainder 1: 3- 2= 1.  Replacing that "2" by "5- 3= 2", 3- (5- 3)= 2(3)- 5= 1.  Replacing that "3" with "8- 5", 2(8- 5)- 5= 2(8)- 3(5)= 1.  Replacing that "5" with 13- 8= 5, 2(8)- 3(13- 8)= 5(8)- 3(13)= 1.  Finally, replacing that "8" by "60- 4(13)", 5(60- 4(13))- 3(13)= 5(60)- 23(13)= 13(-23)+ 60(-5)= 1.  So one solution is x= -23, y= 5.  But it is easy to see that x= -23+ 60i, y= 5+ 12i is also a solution for any i: 13(-23+ 60i)+ 60(5+ 12i)= -299+ 780i+ 300- 780i= 1.  To get the smallest positive value for x take i= 1, x= -23+ 60= 37, the answer you get.
