← Back to Middle school

Middle school🔢Arithmetic●●○○○· 4 min

🧩

Find the GCD without a single division

Euclid's algorithm, mental version: subtract the small from the big until you get the same value. That's the GCD.

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?

#GCD#Euclid#arithmetic#subtraction

You might also like