Euclid's Algorithm

Tags: algorithm

Is an algorithm for finding the greatest common divisor of two integers, $a, b$ .

def gcd(a, b):
    if a < b:
	a, b = b, a
    while b != 0:
	a, b = b, a % b
    return a

Code Snippet 1: Implementation of euclids algorithm.

Procedure

The algorithm proceeds in a series of steps where the output of the last step is used as the input for the next one. At each step $k$ , beginning with $k = 0$ , we find the quotient $q_{k}$ and remainder $r_{k}$ that satisfy the equation $r_{k - 2} = q_{k} r_{k - 1} + r_{k}$ with $r_{- 2} = a$ and $r_{- 1} = b$ . This forms the series:

$\begin{aligned} a & = q_{0} b + r_{0} b & = q_{1} r_{0} + r_{1} r_{0} & = q_{2} r_{1} + r_{2} r_{1} & = q_{3} r_{2} + r_{3} ⋮ \end{aligned}$

This series continues until the remainder $r_{n}$ is 0, at which point the greatest common divisor of $a, b$ is found to be $r_{n - 1}$ . Note: This is guaranteed to happen because the remainders decrease with every step but can never become negative.

Note: if $a < b$ then the first step of the algorithm swaps their orders, otherwise the initial quotient $q_{0}$ is 0 and $r_{0}$ is $a$ , making $r_{k}$ smaller than its predecessor $r_{k - 1} \forall k \geq 0$ .

Proof of Correctness proof

The algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. That is if $A = B \times Q + R$ , then $gcd (A, B) = gcd (B, R)$ .

From the Quotient Remainder Theorem we know any number $A$ can be re-written as $A = B \times Q + R$ . Suppose we know that $D = gcd (A, B)$ then we can write $A = D S$ and $B = D T$ because $D$ is a factor of both $A$ and $B$ . We can then substitute these values for $A, B$ back into the original equation to get $D S = D T Q + R$ . The left hand side in this case is divisible by $D$ meaning the right hand side, $D T Q + R$ , must also be divisible by $D$ . Because $D T Q$ is divisible by $D$ we must conclude $R$ is also divisible by $D$ because $D T Q + R$ is.

Now lets summarise the information we have. We have 3 integers $A, B, R$ which are all divisible by $gcd (A, B)$ . We also know $A = B Q + R$ . Because $a \geq b > r$ we have two cases:

If $R = 0$ then $A = B Q$ and so $B$ divides both $B$ and $A$ so $gcd (A, B) = B$ .
Otherwise ( $r > 0$ ) we can reduce the problem of $gcd (A, B)$ to $gcd (B, R)$ because $A$ , $B$ , & $R$ are all divisible by the same number $D = gcd (A, B)$ . If the highest factor between $A$ and $B$ is $D$ then the highest factor between $B$ and $R$ must also be $D$ .
Because $r < b$ this reduction only needs to be applied a finite number of times before we reach $r = 0$ and terminate.

This proof was heavily sourced from this stack-overflow answer.