Get integer solutions for $13x\equiv1\pmod{60}$ by euclidean method

Question

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)...

Answer 1

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.

Answer 2

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}$.

Answer 3

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.