Calculate gcd(462, 132) by Euclid's algorithm

Step by step

The question

Question: find gcd(462, 132) by Euclid's algorithm.

1 Divide the bigger by the smaller

Divide the bigger number by the smaller: 132 goes into 462 3 times, and 66 is left over.

Here is the trick.

A number that goes into 462 and 132 also goes into 66, because 66 is 462 minus 3 × 132.

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

2 Keep going

Now the same with 132 and 66: 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: 66.

The last remainder that is not 0 is 66.

So gcd(462, 132) = 66.

4 Check

66 goes into both: 462 ÷ 66 is 7, and 132 ÷ 66 is 2.

And 7 and 2 have no common factor, so nothing bigger than 66 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.