Step by step
The question
Question: write gcd(48, 18) as 48x + 18y, with whole numbers x and y.
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 Go back up
Start from the second last row, written for 6: 6 = 18 − 1 × 12.
12 is the remainder of the row above: 48 − 2 × 18.
Swap it in.
Open the bracket and count the 18s: 1 + 1 × 2 = 3.
So x = −1 and y = 3.
5 Check
Put them in: 48 × (−1) plus 18 × 3 is 6.
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.