Step by step
The question
Question: find gcd(299, 221) by Euclid's algorithm.
1 Divide the bigger by the smaller
Divide the bigger number by the smaller: 221 goes into 299 once, and 78 is left over.
Here is the trick.
A number that goes into 299 and 221 also goes into 78, because 78 is 299 minus 1 × 221.
So the gcd does not change, and the numbers get smaller.
2 Keep going
Now the same with 221 and 78: the divisor moves left, the remainder becomes the new divisor.
78 = 1 × 65 + 13.
65 = 5 × 13, 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: 13.
The last remainder that is not 0 is 13.
So gcd(299, 221) = 13.
4 Check
13 goes into both: 299 ÷ 13 is 23, and 221 ÷ 13 is 17.
And 23 and 17 have no common factor, so nothing bigger than 13 goes into both.
Right!
Let's look back.
First: divide the bigger by the smaller.
Then: keep going.
Then: the last remainder before 0.
Last: check.