What is the Euclidean Algorithm?

The Euclidean Algorithm finds the greatest common divisor (GCD) of two integers. It works by repeatedly replacing the larger number by the remainder when divided by the smaller number.

While b ≠ 0:
    (a, b) = (b, a % b)
The GCD is the final value of a.

The key insight: if d divides both a and b, then d also divides a % b (the remainder). So gcd(a, b) = gcd(b, a % b). By iterating this, the numbers shrink exponentially fast — you get the GCD in just a handful of steps even for numbers in the hundreds.

In our puzzle, you're given two integers. Run the Euclidean algorithm and count the number of division steps. The step count mod 26 gives you a letter.

A Concrete Example

Let's work through an example with a = 120 and b = 48.

Step 1: Divide 120 by 48

120 ÷ 48 = 2 remainder 24
Step count: 1
New pair: (48, 24)

Step 2: Divide 48 by 24

48 ÷ 24 = 2 remainder 0
Step count: 2
New pair: (24, 0) — b = 0, so we stop.

Step 3: Count steps and map to a letter

Steps = 2
2 % 26 = 2 → 'c' (a=0, b=1, c=2)

The answer letter is 'c'.

For reference, the GCD of 120 and 48 is 24 (the last non-zero remainder).

Another example: a = 100, b = 36

Step 1: 100 ÷ 36 = 2 rem 28 → (36, 28)
Step 2: 36 ÷ 28 = 1 rem 8  → (28, 8)
Step 3: 28 ÷ 8  = 3 rem 4  → (8, 4)
Step 4: 8 ÷ 4   = 2 rem 0  → (4, 0) — stop!
Steps = 4
4 % 26 = 4 → 'e'

Why It Works: Number Theory in One Paragraph

gcd(a, b) = gcd(b, a mod b). If a number d divides both a and b, then a = d × m and b = d × n for some integers m, n. The remainder r = a - q × b = d × (m - q × n) is also divisible by d. So any common divisor of a and b is also a divisor of b and r, meaning the set of common divisors doesn't change when you replace (a, b) with (b, a mod b). The algorithm reduces the numbers each step because the remainder is always less than b. Since the numbers decrease, the process must terminate — and when b = 0, you've found the GCD (the last non-zero remainder). This proof is over 2,300 years old and appears in Euclid's Elements, Book VII.

Solving Tips

• Implement the loop: while b != 0: a, b = b, a % b; steps += 1
• Count each time you replace (a, b) with (b, a % b)
• Stop when b = 0 — that final step doesn't count for step purposes (or counts as the last step — check the puzzle description)
• Take steps mod 26 and convert to a letter a-z
• For numbers between 50-500, you'll typically get 2-5 steps
• The algorithm is extremely fast — this is one of the easiest puzzles

Difficulty Table

Real-World Applications

• RSA Encryption: The RSA algorithm, which secures nearly all internet traffic, requires computing the GCD to find the decryption key. Euclid's algorithm is used daily billions of times.
• Rational Arithmetic: When adding fractions, you need the GCD to reduce the denominator. Every programming language's rational number library uses Euclid's algorithm.
• Continued Fractions: The Euclidean algorithm produces the continued fraction expansion of a rational number, which is used in Diophantine approximation and music theory.
• Polynomial GCD: The same algorithm works for polynomials — used in computer algebra systems like Mathematica and SymPy.
• Cryptography: The Extended Euclidean Algorithm (which also finds Bézout coefficients) is essential for computing modular inverses in elliptic curve cryptography, Diffie-Hellman key exchange, and nearly every public-key cryptosystem.

Want to Try It?

Head over to the puzzle browser and try it!