GCD and Euclid

The Idea

The greatest common divisor is the longest ruler that measures both numbers exactly.

Lay the shorter length along the longer one. Whatever sticks out must also be measurable by that ruler, so gcd(a, b) becomes gcd(b, a % b). The pair collapses within a handful of divisions, and a remainder of zero names the answer.

Real-World Example

Video tools use it to simplify aspect ratios: 1920 by 1080 shares a gcd of 120, which is how the label "16:9" appears. The same reduction keeps fractions tidy in layout engines and billing code, where floating point would drift.

The Code

def gcd(a, b):
    while b:                 # stop when nothing is left over
        a, b = b, a % b      # the leftover becomes the next divisor
    return a

print(gcd(48, 18))                  # 6
print(gcd(18, 48))                  # 6   -> the first pass just swaps them
print(gcd(13, 7))                   # 1   -> coprime, no shared ruler
print(48 * 18 // gcd(48, 18))       # 144 -> lcm comes free

def gcd(a, b):
    while b:
        a, b = b, ___
    return a