DSA Factory
Free lessonsMath and bits · Stage 0 · Digits and divisibility · Step 4

Euclid's shortcut

Find the greatest common divisor by taking remainders. About 8 minutes.

The greatest common divisor

You have a floor 48 cm by 18 cm and want square tiles that fit exactly, with no cutting. The biggest tile that works is 6 cm, and that 6 is the greatest common divisor of 48 and 18: the largest number that divides both.

Trying every size from the smaller number downwards works, but for numbers near a trillion it is hopeless.

Greatest common divisor: is the biggest number that divides both.
gcd(48, 18)
48
0
18
1
12
2
6
3
0
4
ab

a = 48, b = 18. 48 % 18 = 12.

Move 1 of 4

Swap in the remainder

Euclid's trick: lay 18 cm tiles along the 48 cm side. Two fit and 12 cm is left over. Anything that fits both 48 and 18 must also fit that leftover 12, so the question shrinks to 18 and 12. Then 12 and 6, then 6 and 0.

When the second number reaches 0, the first one is the answer.

Replace the pair: with the second number and the remainder, until the second is 0.
Update both at once: save the remainder before you overwrite the first number.
In code
while b != 0:
    a, b = b, a % b
return a
Quick check

What is the next pair after (35, 15) in Euclid's method?

  1. A(15, 5)
  2. B(20, 15)
  3. C(15, 35)
Show the answer

(15, 5). 35 % 15 = 5, so (a, b) becomes (15, 5). One more round gives (5, 0): the gcd is 5.

Your problem

Greatest common divisor

Return the greatest number that divides both a and b with no remainder. The numbers can be as large as a trillion, so trying every candidate will be too slow.

Example
a = 48, b = 18 → 6

1 ≤ a, b ≤ 1,000,000,000,000 (use longs)

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding