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