Find the GCD without a single division

The algorithm in 1 sentence

The GCD of two numbers doesn’t change if you replace the bigger one with its difference with the smaller.

Example step by step: GCD(84, 30)

Step	Operation	Result
1	$84 - 30$	$(54, 30)$
2	$54 - 30$	$(24, 30)$
3	$30 - 24$	$(24, 6)$
4	$24 - 6$	$(18, 6)$
5	$18 - 6$	$(12, 6)$
6	$12 - 6$	$(6, 6)$ ✓

GCD(84, 30) = 6.

The « division » version (faster)

Instead of subtracting many times, take the remainder of the division:

• $84 = 2 \times 30 + 24$ → GCD(30, 24)
• $30 = 1 \times 24 + 6$ → GCD(24, 6)
• $24 = 4 \times 6 + 0$ → GCD = 6.

This is the classic Euclidean algorithm.

Spot-the-shortcut

If both numbers end in the same even digit, try 2 as a factor. If both are multiples of 3 (digit sum), try 3. Skip the algorithm.

?Your turn

What is the GCD of 48 and 36?

A.6B.12C.18D.24

Check