Find the highest common factor of two or more whole numbers — the biggest number that divides evenly into all of them. This is also called the greatest common divisor (GCD).
The larger number is divided by the smaller, and the remainder is kept.
The process repeats with the smaller number and that remainder.
When the remainder reaches zero, the last non-zero value is the HCF.
For more than two numbers, the HCF is found for the first pair and then carried forward through the list.
Euclidean algorithm: GCD(a, b) = GCD(b, a mod b)
Stop when: b = 0, then a is the GCD
Relationship: HCF × LCM = a × b
Finding the HCF of 12 and 18.
Numbers: 12, 18
18 ÷ 12 leaves a remainder of 6
12 ÷ 6 leaves a remainder of 0
The last non-zero remainder is 6
Answer: HCF = 6
Are HCF and GCD the same thing?
Yes. 'Highest common factor' is the term used in Indian and British schools. 'Greatest common divisor' is more common in the US and in computer science. They mean exactly the same thing.
What does an HCF of 1 mean?
The numbers are called coprime — they share no common factor except 1. They do not need to be prime numbers themselves. For example, 8 and 9 are coprime, even though neither one is a prime number.
Why is the Euclidean algorithm used?
It is much faster than listing out every factor. Finding the HCF of two large numbers only takes a few divisions, which is why it has been used for over two thousand years.