The Largest Shared Divisor
The greatest common factor — also called the greatest common divisor or highest common factor — is the largest number dividing evenly into every value in a set. Its main use is reducing fractions: 48/180 divided by their GCF of 12 gives 4/15, which is the fraction in lowest terms.
The Euclidean Algorithm
Over two thousand years old and still the fastest general method. Divide the larger number by the smaller, then replace the pair with the divisor and the remainder, repeating until the remainder is zero:
| Step | Division | Remainder |
|---|---|---|
| 1 | 180 = 3 × 48 + 36 | 36 |
| 2 | 48 = 1 × 36 + 12 | 12 |
| 3 | 36 = 3 × 12 + 0 | 0 |
The last non-zero remainder is the GCF: 12. The algorithm finishes in a number of steps proportional to the number of digits, which is why it remains the basis of modern implementations including those in cryptography.
Prime Factorisation Method
Factorise each number and take the lowest power of every prime they share:
| Number | Prime factorisation |
|---|---|
| 48 | 2⁴ × 3 |
| 180 | 2² × 3² × 5 |
| 240 | 2⁴ × 3 × 5 |
| GCF | 2² × 3 = 12 |
This method is more transparent and handles several numbers at once, but factorising large numbers is slow — a difficulty that RSA encryption depends on.
Coprime Numbers
Two numbers with a GCF of 1 are coprime, sharing no factor except one. 8 and 9 are coprime despite neither being prime. Coprimality matters in modular arithmetic, in reducing fractions to lowest terms, and in the design of gear systems where even wear is desired.
Where It Is Used
- Simplifying fractions — dividing by the GCF gives lowest terms in one step.
- Simplifying ratios — the same operation.
- Dividing into equal groups — the largest possible group size that leaves nothing over.
- Cryptography — the extended Euclidean algorithm computes modular inverses, which RSA key generation requires.
Frequently Asked Questions
What is the GCF of two primes?
Always 1, unless they are the same prime. Distinct primes share no factors.
Can the GCF be larger than the smallest number?
No. It must divide every number, so it is at most the smallest one — and equals it when that number divides all the others.
Is GCF the same as HCF?
Yes. Greatest common factor, greatest common divisor and highest common factor are three names for the same thing, differing by country and textbook.