Euclidean Algorithm Algorithm Tutorial

Euclidean Algorithm for GCD

The Greatest Common Divisor (GCD), also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF), is the largest number that divides both inputs. The Euclidean algorithm computes GCD efficiently using the property $gcd(a, b) = gcd(b, a \mod b)$.

Any common divisor of $a$ and $b$ also divides $a \mod b$. So you preserve the GCD through the modulo operation. Eventually, you reach $gcd(n, 0) = n$.

function gcd(a, b):
    while b != 0:
        temp = b
        b = a mod b
        a = temp
    return a

Recursive version:

function gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a mod b)

Example trace: $gcd(48, 18)$ $1.$ $gcd(48, 18) \to gcd(18, 12)$ $2.$ $gcd(18, 12) \to gcd(12, 6)$ $3.$ $gcd(12, 6) \to gcd(6, 0)$ $4.$ Return $6$

Applications: You use GCD for simplifying fractions, cryptography (RSA), finding LCM, and solving Diophantine equations.

Time complexity: $O(\log(\min(a, b)))$ because the remainder decreases by at least half every $2$ steps.

Space complexity: $O(1)$ for iterative, $O(\log(\min(a, b)))$ for recursive due to call stack.