Step by step
The question
Question: find gcd(56, 42) by Euclid's algorithm.
1 Divide the bigger by the smaller
Divide the bigger number by the smaller: 42 goes into 56 once, and 14 is left over.
Here is the trick.
A number that goes into 56 and 42 also goes into 14, because 14 is 56 minus 1 × 42.
So the gcd does not change, and the numbers get smaller.
2 Keep going
Now the same with 42 and 14: the divisor moves left, the remainder becomes the new divisor.
3 The last remainder before 0
Careful!
0 only tells us to stop.
The answer is the last remainder before it: 14.
The last remainder that is not 0 is 14.
So gcd(56, 42) = 14.
4 Check
14 goes into both: 56 ÷ 14 is 4, and 42 ÷ 14 is 3.
And 4 and 3 have no common factor, so nothing bigger than 14 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.