Calculate gcd(84, 36) by Euclid's algorithm

Step by step

The question

Question: find gcd(84, 36) by Euclid's algorithm.

1 Divide the bigger by the smaller

Divide the bigger number by the smaller: 36 goes into 84 2 times, and 12 is left over.

Here is the trick.

A number that goes into 84 and 36 also goes into 12, because 12 is 84 minus 2 × 36.

So the gcd does not change, and the numbers get smaller.

2 Keep going

Now the same with 36 and 12: the divisor moves left, the remainder becomes the new divisor.

3 The last remainder before 0

Careful!

0 only tells us to stop.

The answer is the last remainder before it: 12.

The last remainder that is not 0 is 12.

So gcd(84, 36) = 12.

4 Check

12 goes into both: 84 ÷ 12 is 7, and 36 ÷ 12 is 3.

And 7 and 3 have no common factor, so nothing bigger than 12 goes into both.

Right!

Let's look back.

First: divide the bigger by the smaller.

Then: keep going.

Then: the last remainder before 0.

Last: check.