← Iris
Lab / Experiment

Euclidean Algorithm

The oldest known algorithm. Enter two numbers and watch the GCD emerge through repeated division. The rectangle-cutting visualization shows the geometric interpretation — each step cuts the largest possible squares from a rectangle, and the final square tile is the GCD.

Enter two numbers and press Run to begin.

Result

GCD(a, b) —
Steps taken —
a / GCD —
b / GCD —

Input

a —
b —
Mode Basic

Rectangle cutting

Current step squares
Previous step squares
GCD square (final)
Enter two positive integers and press Run or Enter  ·  Step advances one step at a time  ·  Random picks two numbers  ·  Switch to Extended mode to see Bézout coefficients

What’s happening

The Euclidean algorithm

Described by Euclid around 300 BCE in Book VII of the Elements, this is the oldest known algorithm still in common use. Given two positive integers a and b, repeatedly replace the larger with the remainder of dividing it by the smaller. When the remainder reaches zero, the other number is the GCD.

The algorithm

function gcd(a, b):
    while b ≠ 0:
        q = floor(a / b)
        r = a - q * b     // a mod b
        a = b
        b = r
    return a

The rectangle-cutting interpretation

Think of a and b as the sides of a rectangle. Cut out the largest possible squares (side = shorter dimension). The remaining rectangle has dimensions equal to the shorter side and the remainder. Repeat until the rectangle is perfectly tiled by squares. That final square side is the GCD — it’s the largest square that tiles the original rectangle exactly.

The extended Euclidean algorithm

Bézout’s identity guarantees that for any integers a and b, there exist integers x and y such that a·x + b·y = gcd(a, b). The extended Euclidean algorithm finds x and y by working backwards through the division steps. This is the mathematical foundation of RSA encryption, modular inverses, and the Chinese Remainder Theorem.

Complexity

Lamé proved in 1844 that the number of steps is at most five times the number of digits in the smaller number. The worst case occurs when a and b are consecutive Fibonacci numbers — the golden ratio slows convergence as much as possible. For gcd(Fn+1, Fn), the algorithm takes exactly n steps.

Why it matters

The Euclidean algorithm is everywhere in mathematics and computer science. It simplifies fractions, computes modular inverses for cryptography, solves linear Diophantine equations, constructs continued fractions, and underlies the RSA algorithm that secures the internet. Twenty-three centuries old, and still indispensable.