How to calclulate 1/17 mod 60

Question

how can I calculate $ d = 17^{-1} (\text{mod} ~ 60) $ ? I was reading this article and then I wrote down this steps:

60 = 3 * 17 + 9
17 = 1 * 9 + 8
9 = 1 * 8 + 1

In the end (using EEA) I get x = -1 and y = 4. But if I insert x, y like this way: $60 * -1 + 17^{-1} * 4 $ I dont get 0.588..

What do I wrong?

Best :D

Answer 1

$60 = 17\cdot 3 + 9$
$17 = 9\cdot 1 + 8$
$9 = 8\cdot1 + 1$

$1 = (9 - 8) = (9 - (17 - 9)) = (2\cdot 9 - 17) = (2\cdot (60-17\cdot 3) -17) = 2\cdot 60 - 7\cdot 17$

So $17\cdot -7 \mod_{60} = 1$

Thus $53$ is the inverse.

Answer 2

Here is the (simplified) layout of the EEA: $$\begin{array}{cccc} r_i&u_i&v_i&q_i\\ \hline 60&0&1\\17&1&0&3\\\hline 9&-3&1&1\\8&4&-1&1\\1&-7&2\\\hline \end{array}$$ where $r_i, q_i$ are the remainder and quotient at step $i$ of the Euclidean algorithm, and $u_i,v_i$ are the Bézout's coefficients of each of the remainders. The recurrence relation is $$u_{i+1}=u_{i-1}- q_iu_i,$$ and similarly for the $v_i$s.

The result of this algorithm says that$\;-7\cdot 17+2\cdot 60=1$, whence $-7\cdot 17\equiv 1\mod 60$. This means $17^{-1}\equiv-7\equiv 53\mod 60$.

Answer 3

You didn't go far enough.

$60 = 3*17 + 9 \implies 9 = 60 - 3*17$

$17 = 9 + 8 \implies 8 = 17 - 9 = 17 - (60-3*17) = 4*17 - 60$

This is as far as you went. Need to go one step further.

$9 = 8 + 1 \implies 1 = 9 - 8 = (60-3*17) - (4*17 -60) = 2*60 - 7*17$

So $-7*17 \equiv 1 \mod 60$ and $-7 \equiv 53 \equiv \frac 1 {17} \mod 60$.

(To get an x,y with y = 53 rather than -7: $1= 2*60 - 7*17 = 2*60 - 7*17 + 60*17 - 60*17= (2-17)*60 + 53*7 = -15*60 + 53*17$)

I don't understand what $60*2 - 7/17$ is supposed to signify.

But $60*2 - 7*17 = 1$ so $60*2/17 - 7 = \frac 1{17}=.058...$ for what that's worth.

... and $60*\frac{-15}{17} + 53 = \frac 1{17}= .058...$.