Step by step
The question
Question: write gcd(161, 28) as 161x + 28y, with whole numbers x and y.
1 Divide the bigger by the smaller
Divide the bigger number by the smaller: 28 goes into 161 5 times, and 21 is left over.
Here is the trick.
A number that goes into 161 and 28 also goes into 21, because 21 is 161 minus 5 × 28.
So the gcd does not change, and the numbers get smaller.
2 Keep going
Now the same with 28 and 21: the divisor moves left, the remainder becomes the new divisor.
21 = 3 × 7, 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: 7.
The last remainder that is not 0 is 7.
So gcd(161, 28) = 7.
4 Go back up
Start from the second last row, written for 7: 7 = 28 − 1 × 21.
21 is the remainder of the row above: 161 − 5 × 28.
Swap it in.
Open the bracket and count the 28s: 1 + 1 × 5 = 6.
So x = −1 and y = 6.
5 Check
Put them in: 161 × (−1) plus 28 × 6 is 7.
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.