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

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{align*} 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 \
\vdots \end{align*}

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 \( DS = DTQ + R \). The left hand side in this case is divisible by \( D \) meaning the right hand side, \( DTQ + R \), must also be divisible by \( D \). Because \( DTQ \) is divisible by \( D \) we must conclude \( R \) is also divisible by \( D \) because \( DTQ + 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 = BQ \) 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.