How did Euclid find greatest common denominator for greatest common factor?

Euclid's method is great for extremely large numbers - numbers which are extremely hard to factor. It doesn't require you to figure out the factors.I think the method is best explained with an example. Suppose you want the greatest common factor of 14 and 10.

This is the same as the gcf of 10 and 4 - where 4 is the REMAINDER of the division of 14 by 10 (if you divide 14 by 10, you get 1, with a reminder of 4).

Repeat: gcf(10, 4) = gcf(4, 2) - once again, the 2 is obtained as the remainder of the division, in this case, of 10 by 4.

gcf(4, 2) = gcf(2, 0) - in this case, the remainder is zero.

As soon as one of the numbers is zero, the other is the answer:

gcf(2, 0) = 2