Step by step
The question
Question: find gcd(91, 35) by Euclid's algorithm.
1 Divide the bigger by the smaller
Divide the bigger number by the smaller: 35 goes into 91 2 times, and 21 is left over.
Here is the trick.
A number that goes into 91 and 35 also goes into 21, because 21 is 91 minus 2 × 35.
So the gcd does not change, and the numbers get smaller.
2 Keep going
Now the same with 35 and 21: the divisor moves left, the remainder becomes the new divisor.
21 = 1 × 14 + 7.
14 = 2 × 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(91, 35) = 7.
4 Check
7 goes into both: 91 ÷ 7 is 13, and 35 ÷ 7 is 5.
And 13 and 5 have no common factor, so nothing bigger than 7 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.