Can you please solve $7^{-1} \mod 480$ using extended Euclidean Algorithm?. Kindly show the steps till end

Question

I am solving RSA algorithm wherein I have to find d by finding $7$ inverse modulo $480$. Please help in solving till end using extended euclidean algorithm

Using extended Euclidean Algorithm for finding inverse as follows:

$$480 = 7(68) + 4$$ $$68 = 4(17) + 0$$

Now, I am getting remainder 0 here. How shall I proceed ahead after this first step

Answer 1

$480 = 7*68 + 4$ so $4 = 480 - 7*68$

$7 = 4 + 3$ so $3 = 7-4$

$4 = 3 + 1$ so $1 = 4 - 3$

So $1 = 4-3=$

$(480 - 7*68) - (7-4)=$

$(480-7*68) - (7-(480 - 7*68))=$

$(480-7*68) -(7*69 - 480)=$ $2*480 - 137*7$

=====

So how do you solve $7k \equiv 1 \pmod{480}$?

Answer 2

Here is how I do it and keep myself organized

$\begin {array}{crl} \times480&\times 7\\ 1&0&480\\ 0&1&7\\ 0&68&476\\ 1&-68&4\\ 2&-136&8\\ 2&-137&1 \end{array}$

Number in the first column, I multiply by 480. The number in the second column, I multiply by 7. The third column is their sum.

I do what are effectively matrix row operations to the right column as far as it will go.

$480\times2 + (-137\times 7) = 1$

$-137\equiv 343 \equiv 7^{-1}\pmod{480} $

Worth noting:

$343 = 7^3\\ 7^4\equiv 1\pmod{480}$

Answer 3

By here $\,\ \overbrace{7^{-1}_{480} \equiv \dfrac{1-480(\color{#c00}{480^{-1}_7})}7}^{\rm\large inverse\ reciprocity}\equiv \dfrac{1-480(\color{#c00}2)}7\equiv -137,\ $ by $\bmod 7\!:\ \color{#c00}{\dfrac{1}{480}}\equiv \dfrac{8}4\equiv\color{#c00} 2$

Answer 4

My computation of the gcd of $480$ and $7$ in tabular form:

$$ \begin{matrix} 480 & - & 1 & 0\\ 7 & 68 & 0 & 1\\ 4 & 1 & 1 & -68\\ 3 & 1 & -1 & 69\\ 1 & - & 2 & -137\\ \end{matrix}$$

(where the second column has the quotients $q$, and we subtract $q$ times the row of two after it from the row of $2$ above it, for the last two columns. We stop when we reach divisibility as with $1$ and $3$.
So we get $$1 = 2 \cdot 480 + (-137) \cdot 7$$

which we take modulo $480$ and get $$7^{-1} \equiv -137 \equiv 343 \pmod{480}$$

So, e.g. when in RSA we have $\phi(n)=480$ and $e=7$ we take $d=343$.