Finding $d$ such that $ed \equiv 1 \bmod{n}$, given $e$ and $n$, with pen and paper

Question

I have tried to run Euclid's algorithm in reverse to solve this problem but i'm not sure that it works. As above (in the title) the problem is to find mod($d \times e$,$n$)=1, given $e=7$ and $n=3120$ find $d$. One answer using MATLAB is 1783, but I am looking for pen and paper method.

Answer 1

You want a solution of $7d+3120k=1$. I learned the method as follows: run Euclid's algorithm on $7$ and $3120$ in the top row of the matrix, carry out the same operations on letters $a,b$ in the bottom row. $$\begin{pmatrix} 7 & 3120 \\ a & b \end{pmatrix} \to \begin{pmatrix} 7 & -2 \\ a & b-446a \end{pmatrix} \to \begin{pmatrix} 1 & -2 \\ -1337a +3b & b-446 \end{pmatrix} $$ So, $-1337\cdot 7 +3\cdot 3120=1$. This gives $d=-1337$, which may be negative but I like it.

(Adding $3120$ yields your answer.)

Answer 2

$$3120=7(445)+5.$$ $$7=5(1)+2.$$ $$5=2(3)-1.$$ $$\text {Therefore }\quad 1=-5+3(2)=-5+3(7-5(1))=-4(5)+3(7)=$$ $$=-4(3120-7(445))+3(7)=$$ $$=3120(-4)+7((445)(4)+3)=3120(-4)+7(1783).$$

OR, since $5$ and $7$ are small we can easily see that $4(5)=7(3)-1$ and take a short-cut : $4(3120) =4(7(445)+5)=7(4)(445)+3(7)-1$ so we have $1\equiv 7(4(445)+3)\equiv 7 (1783)\pmod {3120}.$

Note that at the step $5=2(3)-1$ we do not have to use $5=2(2)+1.$ It suffices that $5=2(x)+y$ with $|y|<2,$ and taking $y=-1$ is more convenient here. We can do this at the first step: $3120=7(446)-2,$ and have a shorter short-cut.