Write gcd(84, 36) as 84x + 36y

Step by step

The question

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

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 Go back up

Start from the second last row, written for 12: 12 = 84 − 2 × 36.

So x = 1 and y = −2.

5 Check

Put them in: 84 × 1 plus 36 × (−2) is 12.

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.