Highest Common Factors – Euclid's algorithm

The Maths

A factor is a whole number which divides into a bigger number with no remainder.

So, 4 is factor of 16.

2 and 8 are also factors of 16. And 1 is always a factor of any other whole number.

So 16 has four factors: 1, 2, 4 and 8. These are the only numbers that will divide into 16 without a remainder.

A common factor is a number that will divide into two bigger numbers with no remainder.

So, the common factors of 24 and 16 are: 1, 2, 4, and 8. These are the four numbers that will divide both into 24 and 16 without any remainder.

The Highest Common Factor of two numbers is the biggest number that will divide into both of those numbers without a remainder.

So, the Highest Common Factor of 24 and 16 is 8. This is the biggest number that will divide into both 24 and 16 without leaving a remainder.

Some questions:

  1. What is the Highest Common Factor of 25 and 20?
  2. What is the Highest Common Factor of 30 and 24?
  3. What is the Highest Common Factor of 40 and 10?
  4. What is the Highest Common Factor of 27 and 17?

That's all very well, and not too difficult. But what's this got to do with Computing?