Calculate gcd(100, 75) by Euclid's algorithm

Step by step

The question

Question: find gcd(100, 75) by Euclid's algorithm.

1 Divide the bigger by the smaller

Divide the bigger number by the smaller: 75 goes into 100 once, and 25 is left over.

Here is the trick.

A number that goes into 100 and 75 also goes into 25, because 25 is 100 minus 1 × 75.

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

2 Keep going

Now the same with 75 and 25: 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: 25.

The last remainder that is not 0 is 25.

So gcd(100, 75) = 25.

4 Check

25 goes into both: 100 ÷ 25 is 4, and 75 ÷ 25 is 3.

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