Euclidean Algorithm

Objective

The Euclidean Algorithm efficiently computes the Greatest Common Divisor (GCD) of two integers AA and BB.

The core idea is based on the following identity:

gcd(A,B)=gcd(B,AmodB)\gcd(A, B) = \gcd(B, A \bmod B)

Code

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

Proof

Let G=gcd(A,B)G = \gcd(A, B). Then, we can write A=aGA=aG, B=bGB=bG, where aa and bb are coprime integers.

Dividing AA by BB gives:

A=Bq+RA = Bq + R

Then:

R=ABq=(abq)G=rGR = A - Bq = (a - bq)G = rG

So R=rGR = rG, and we want to prove that gcd(B,R)=G\gcd(B, R) = G is true if and only if bb and rr are coprime.

Suppose, for contradiction, that bb and rr are not coprime. Then there exists a common divisor m>1m > 1 such that:

b=mb,r=mrb = mb', \quad r = mr'

where bb' and rr' are coprime. Then:

a=bq+r=mbq+mr=m(bq+r)\begin{align*} a &= bq + r \\ &= mb'q + mr' \\ &= m(b'q + r') \end{align*}

This means aa is also divisible by mm, implying aa and bb share a common factor mm, contradicting the assumption that aa and bb are coprime. Thus, bb and rr must be coprime.

Proving the reverse is trivial, so we don't prove it here.

Written by ryan Kim from A41

Last updated