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