Euclidean algorithm to find inverse modulo
Find an inverse for $43$ modulo $600$ that lies between $1$ and $600$, i.e., find an integer $1 \leq t \leq 600$ such that $43 \cdot t \equiv 1 (\text{ mod } 600)$.
The solution below states $600 = 43 \cdot 15+15$ which is in fact $660$, but somehow it still arrives at the correct answer of $307$?
2 Answers
$\begingroup$This is a coincidence, and this is how it happened:
Because of the miscalculation, we now found the inverse of 43 modulo 660. We found that $1=43\cdot307-660\cdot20$. But coincidently, we have $660\cdot20=13200=600\cdot22$, so $1=43\cdot307-600\cdot22$. This means that we also have found the inverse of 43 modulo 600.
Edit: We can do the same trick for any divisor of 13200. Take 825 for example. We get $1=43\cdot307-825\cdot16$, so we also have found the inverse of 43 modulo 825.
$\endgroup$ $\begingroup$Because $43 \cdot 307 = 13201 \implies 13201 \text{ mod } 600 = 1$
That is the same to say
$$43 \cdot 307 \equiv 1 (\text{ mod } 600)$$
For more information see: Modular-inverses and wiki modular-inverses
$\endgroup$
