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