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


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.
