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