How did Euclid find the greatest common factor?

Answer 1

If the two numbers are the same then the GCF is the common value. Otherwise:

1. find the difference between the larger number and the smaller number.
2. replace the larger of the two numbers by this difference.
3. if the two numbers are the same then that is the GCF, but if not go back to step 1.

Euclidean Algorithm

It is not necessary to actually list the factors of all numbers to get the GCF for only two numbers. You can use the Euclidean algorithm.

(1) Divide the larger number by the smaller one.

(2) If there is no remainder, the GCF is the same as the smaller number.

(3) Repeat step 1 with the smaller number and the remainder.

Example:

GCF of 51 and 85.

85/51 = 1 R 34

51/34 = 1 R 17

34/17 = 2 R 0<== By step 2, we are done. Our answer is 17.

Lets try one that doesn't reduce -- GCF(17,39)

39/17 = 2 R 5

17/5 = 3 R 2

5/2 = 2 R 1

2/1 = 2 R 0, so our answer, the GCF, is 1.

Answer 2

Suppose you want the greatest common factor, GCF, of A and B.

1. If A = B then B is the GCF. So stop. Otherwise
2. Replace the larger number by the (larger minus the smaller).
   
3. Go to Step 1.

Since the numbers are getting smaller all the time, the process must end. If it ends at 1 then the two numbers are coprime else the last number, B, is the GCF.