Using Euclid's algorithm to find Multiplicative Inverse 71 mod 53

Question

I begin by writing out the recursion until a mod b == 0

53 -> 71-> 53-> 18-> 17 ->1 -> 0

to get in the form $sa+tn$

starting with $1 = 18-17$ I then substitute $17 = 53-(18\cdot2)$

this gives me $18\cdot3-53$

I then substitute $18 = (71-53)$ which gives me

$$71\cdot3 - 53\cdot4$$

this has me stuck because I know I need to substitute $53$ in a form of $x\cdot53-y\cdot71$ but I am unsure how to find this form without a calculator

Answer 1

You have done almost all the work yourself. You just need to interpret what you already have.

Your arrangement in the second last line gives you $71\cdot3-53\cdot4=1$ which on rearrangement is $71\cdot3=53\cdot4 + 1$ which exactly implies by modular property that $3\cdot71=1 \pmod{53}$ i.e. in modulo group $\mathbb{Z}_{53}$, $\overline{3} \cdot \overline{71} = \overline{1}$. So your inverse is $\overline{3}$.