Example

Suppose we want to find x such that $111x\equiv 1 \pmod{257}$.

We use Euclid's algorithm as follows:

$$\begin{array}{ccccccc\vert c\vert c} &&&&&&&0&1\\ \text{Di... ...&44&19 \\ 5 &=& 5 &\cdot & 1 &+& 0 & 257&111 \\ \end{array}$$

• In the latter two columns, we multiply the entry above times the current quotient and add it to the entry two floors above. Example: $37 = 5\cdot 7+2$, $19=1\cdot 16+3$, etc.
• In the step where we finally obtain remainder 1, we always have something like $44\cdot 111 - 19\cdot 257 = \pm 1$. It's +1 if it took an even number of steps, and -1 otherwise. In this case $44\cdot 111 -19\cdot 257 =1$. That means $44\cdot 111 \equiv 1 \pmod{257}$. So our solution is x=44.
• If the final nonzero remainder is greater than 1, that number is the greatest common factor (or divisor) of the two numbers we started out with.

In the latter two columns, we multiply the entry above times the current quotient and add it to the entry two floors above. Example: $37 = 5\cdot 7+2$, $19=1\cdot 16+3$, etc. In the step where we finally obtain remainder 1, we always have something like $44\cdot 111 - 19\cdot 257 = \pm 1$. It's +1 if it took an even number of steps, and -1 otherwise. In this case $44\cdot 111 -19\cdot 257 =1$. That means $44\cdot 111 \equiv 1 \pmod{257}$. So our solution is x=44. If the final nonzero remainder is greater than 1, that number is the greatest common factor (or divisor) of the two numbers we started out with.