Euclid's Algorithm

Euclid's algorithm is used to find the greatest common divisor of two numbers. In its extended form it can calculate the reciprocal a number modulo a prime.

To calculate the gcd of two numbers, $\gcd(a,b)$, where $a>b$ we write $a$ $=$ $bq_1$ $+$ $r_1$ where $q_1$ is the quotient and $r_1$ is the remainder. If the gcd divides $a$ and $b$ it must also divide $r_1$. So we can now take the gcd of $b$ and $r_1$. At each iteration $r_i$ is getting smaller and will eventually be $0$. The gcd of $a$ and $b$ will be the last non-zero remainder.

As an example $\gcd(105,33)$ $=$ $\gcd(33,6)$ $=$ $\gcd(6,3)$ $=$ $3$.

We can back substitute to solve $M$ and $N$ for $aM$ $+$ $bN$ $=$ $\gcd(a,b)$. We have $3$ $=$ $33\times 1$ $-$ $6\times 5$ $=$ $33$ $-$ $(105$ $-$ $33\times 3)\times 5$ $=$ $-105\times 5$ $+$ $33\times 16$. Thus $M$ $=$ $-5$ and $N$ $=$ $16$.

With $aM$ $+$ $bN$ $=$ $1$ we can see that if $b$ was prime then $aM$ $\equiv$ $1$ $\pmod{b}$ or $a^{-1}$ $\equiv$ $M$ $\pmod{b}$.