To see that it is the greatest common factor, we could use a result which is important in its own right and has some amazing consequences.

Fact: The number produced by the Euclidean Algorithm is a difference of multiples of the two original numbers.

To see this we will show how to express the result of the Euclidean Algorithm in our example as a difference of multiples of the two original numbers.



The algorithm gives us a result of 3. The next to the last division problems tells us that

3 = 9 - 6

The problem before that tells us that

6 = 24 - 2(9)

We substitute this value for 6 into the previous equation

3 = 9 - (24 - 2(9))

This enables us to express 3 using 9's and 6's. We simplify by removing parentheses and combining like terms.

= 9 - 24 + 2(9)

or

3 = 3(9) - 24

The reader can do the arithmetic to verify that this is true. This enables us to express 3 as a difference of multiples of 9 and 24.

If we look at the second division problem, we see that

9 = 105 - 4(24)

If we substitute that expression in for the 9 in the previous equation we get

3 = 3(105 - 4(24)) - 24

This enables us to express 3 using multiples of 105 and 24 as required. We can simplify again by removing parentheses and combining like terms.

= 3(105) - 12(24) - 24

or

3 = 3(105) - 13(24)

which is true, because when you do the arithmetic we get

315 - 312 = 3

This will enable us to conclude that the result of the Euclidean Algorithm is the greatest common factor. We have previously seen that it is a common factor. To see that it is the greatest common factor, note that if we have any common factor of 24 and 105 it will go into any multiple of 24 and into any multiple of 105 and hence into any sum or difference of multiples of 24 and 105. Since the number produced by the Euclidean Algorithm is a difference of multiples of the two original numbers, any common factor will go into it. If one whole number goes into another whole number it cannot be bigger than a number that it goes into. As a result, the number produced by the Euclidean Algorithm must be the biggest common factor.

Note that the Euclidean Algorithm allows us to conclude that the greatest common factor is divisible by any other common factor. That is much stronger than just saying that it is the largest of all the common factors.

While the justification just provided is but an example and not a proof, the reader will find that the procedures illustrated in the example will work to find the greatest common factor of any two whole numbers and to express the greatest common factor as a difference of multiples of the original two numbers.

Example

Previous page

Consequence

Euclidean Algorithm