Euclidean Algorithm (GCD)
DSA · Classic Algorithms
Theory
The Euclidean algorithm finds the greatest common divisor (GCD) of two integers: the largest number that divides both. It relies on one fact: gcd(a, b) = gcd(b, a mod b), because any number dividing a and b also divides the remainder. Repeating this replaces the pair with smaller numbers until the remainder is 0; the other number is then the GCD. For 252 and 105: 252 mod 105 = 42, 105 mod 42 = 21, 42 mod 21 = 0, so the GCD is 21. It is over 2,000 years old and still one of the fastest algorithms known, running in O(log min(a, b)) steps. The least common multiple follows directly: lcm(a, b) = a * b / gcd(a, b). The extended version also finds x and y with ax + by = gcd(a, b), which is used for modular inverses in cryptography.
Why we use it
GCD and LCM appear in fraction simplification, scheduling repeating events, ratio problems and RSA cryptography. The algorithm is also the standard first example of a fast recursive algorithm.
When to use it
Use it whenever you need common divisors or multiples. Python's math.gcd and math.lcm implement it for you.
How it works
- gcd(a, b)
- b == 0? Yes: Return a. No: (a, b) = (b, a % b).
- Repeat
Syntax
gcd(a, 0) = a
gcd(a, b) = gcd(b, a % b)
lcm(a, b) = a * b // gcd(a, b)
Time O(log min(a, b))Example
import math
def gcd(a, b):
steps = []
while b:
steps.append(f"gcd({a}, {b})")
a, b = b, a % b
steps.append(f"= {a}")
print(" -> ".join(steps))
return a
gcd(252, 105)
print("math.gcd:", math.gcd(252, 105))
def lcm(a, b):
return a * b // math.gcd(a, b)
print("Buses every 12 and 18 min meet every", lcm(12, 18), "min")
num, den = 84, 126
g = math.gcd(num, den)
print(f"{num}/{den} simplifies to {num // g}/{den // g}")
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
g, x, y = extended_gcd(b, a % b)
return g, y, x - (a // b) * y
g, x, y = extended_gcd(240, 46)
print(f"240*{x} + 46*{y} = {g}")Key points
- gcd(a, b) = gcd(b, a mod b) until the remainder is 0
- Runs in logarithmic time
- lcm(a, b) = a * b / gcd(a, b)
- Extended version gives modular inverses for cryptography