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

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

• " Please solve using extended euclidean algorithm and show all steps till end." that's a very unreasonable request. More reasonable would be help to get you started or a rough outline – fleablood Feb 21 '19 at 20:53
• $\frac{7}{480}=[0;68,1,1,3]$ and $[0;68,1,1]=\frac{2}{137}$ imply $$7\cdot 137-2\cdot 480 = -1,$$ hence the inverse of $7\pmod{480}$ is given by $-137\equiv 343\pmod{480}$. – Jack D'Aurizio Feb 21 '19 at 21:01
• A more efficient technique is probably to find $7^{-1}\pmod{32},\pmod{3},\pmod{5}$, then invoke the Chinese remainder theorem. – Jack D'Aurizio Feb 21 '19 at 21:04
• See here for a very convenient form of the Extended Euclidean Algorithm. – Gone Feb 21 '19 at 22:04
• @Jack Unlikely - it's rare that CRT is more efficient than the Extended Euclidean Algorithm, e.g. it took me $10$ seconds of mental arithmetic in my answer below. – Gone Feb 21 '19 at 22:06

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

• Can you please solve till end – first last Feb 21 '19 at 21:16
• Yes, I can. But I won't. If $1 = 2*480 - 137*7$ then $-137*7 \equiv 1\pmod {480}$. – fleablood Feb 21 '19 at 21:21
• @firstlast You'll find it much easier (and less error prone) to use the method I linked in a comment on your question (similar to the method in Doug's answer). – Gone Feb 21 '19 at 22:12
• Yes. I have to agree with Bill and Doug about the ease of their methods. This was a simple case but the errors one usually has..... (#@%*) – fleablood Feb 21 '19 at 22:19

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

• This is essentially a special case (single step) of the Extended Euclidean Algorithm that is more convenient in certain cases. – Gone Feb 21 '19 at 22:01

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

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