Step by step
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.