Calculate gcd(48, 18) by Euclid's algorithm Easy

The question

Question: find gcd(48, 18) by Euclid's algorithm.

1 Divide the bigger by the smaller

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

Here is the trick.

A number that goes into 48 and 18 also goes into 12, because 12 is 48 minus 2 × 18.

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

2 Keep going

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

12 = 2 × 6, and the remainder is 0.

We stop.

3 The last remainder before 0

Careful!

0 only tells us to stop.

The answer is the last remainder before it: 6.

The last remainder that is not 0 is 6.

So gcd(48, 18) = 6.

4 Check

6 goes into both: 48 ÷ 6 is 8, and 18 ÷ 6 is 3.

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

▶ Watch it solved

Calculate gcd(252, 198) by Euclid's algorithm Medium

The question

Question: find gcd(252, 198) by Euclid's algorithm.

1 Divide the bigger by the smaller

Divide the bigger number by the smaller: 198 goes into 252 once, and 54 is left over.

Here is the trick.

A number that goes into 252 and 198 also goes into 54, because 54 is 252 minus 1 × 198.

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

2 Keep going

Now the same with 198 and 54: the divisor moves left, the remainder becomes the new divisor.

54 = 1 × 36 + 18.

36 = 2 × 18, and the remainder is 0.

We stop.

3 The last remainder before 0

Careful!

0 only tells us to stop.

The answer is the last remainder before it: 18.

The last remainder that is not 0 is 18.

So gcd(252, 198) = 18.

4 Check

18 goes into both: 252 ÷ 18 is 14, and 198 ÷ 18 is 11.

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

▶ Watch it solved

Write gcd(252, 198) as 252x + 198y Harder

The question

Question: write gcd(252, 198) as 252x + 198y, with whole numbers x and y.

1 Divide the bigger by the smaller

Divide the bigger number by the smaller: 198 goes into 252 once, and 54 is left over.

Here is the trick.

A number that goes into 252 and 198 also goes into 54, because 54 is 252 minus 1 × 198.

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

2 Keep going

Now the same with 198 and 54: the divisor moves left, the remainder becomes the new divisor.

54 = 1 × 36 + 18.

36 = 2 × 18, and the remainder is 0.

We stop.

3 The last remainder before 0

Careful!

0 only tells us to stop.

The answer is the last remainder before it: 18.

The last remainder that is not 0 is 18.

So gcd(252, 198) = 18.

4 Go back up

Start from the second last row, written for 18: 18 = 54 − 1 × 36.

36 is the remainder of the row above: 198 − 3 × 54.

Swap it in.

Open the bracket and count the 54s: 1 + 1 × 3 = 4.

54 is the remainder of the row above: 252 − 1 × 198.

Swap it in.

Open the bracket and count the 198s: −1 − 4 × 1 = −5.

So x = 4 and y = −5.

5 Check

Put them in: 252 × 4 plus 198 × (−5) is 18.

Right!

Let's look back.

First: divide the bigger by the smaller.

Then: keep going.

Then: the last remainder before 0.

Then: go back up.

Last: check.

▶ Watch it solved