Extended Euclidean Algorithm

From ProofWiki
Jump to navigation Jump to search


The extended Euclidean algorithm is a method for:

finding the greatest common divisor (GCD) $d$ of two strictly positive integers $m$ and $n$
computing two integers $a$ and $b$ such that $a m + b n = d$.

Let $m, n \in \Z_{>0}$.

$\mathbf 1:$ Initialise.
Set $a' \gets b \gets 1, a \gets b\,' \gets 0, c \gets m, d \gets n$.
$\mathbf 2:$ Divide.
Let $q$ and $r$ be the quotient and remainder respectively of $ c / d$.
(Thus we have $c = q d + r$ such that $0 \le r < d$.)
$\mathbf 3:$ Remainder zero?
If $r = 0$, the algorithm terminates.
(Thus we have $a m + b n = d$ as required.)
$\mathbf 4:$ Recycle.
Set $c \gets d, d \gets r, t \gets a', a' \gets a, a \gets t - q a, t \gets b\,', b\,' \gets b, b \gets t - q b$, then go to Step $\mathbf 2$.



Thus the GCD of $m$ and $n$ is the value of the variable $d$ at the end of the algorithm.