[Math] Euclidean algorithm to find inverse modulo

congruenceseuclidean-algorithmmodular arithmetic

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$?
enter image description here

Best Answer

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.