Greatest Common Factor
Find the Greatest Common Factor (GCF) of two numbers
"Greatest Common Factor" Calculator
How to find the GCF of 12 and 16
The greatest common factor (GCF) of two numbers is the largest natural number that divides both of them; it is also called the GCD or HCF.
12 = 22 × 3
16 = 24
| Prime | 12 | 16 | Lowest power |
|---|---|---|---|
| 2 | 22 | 24 | 22 |
| 3 | 3 | — | — |
— = power 0: the prime is not a factor of this number, so it cannot be in the GCF.
GCF = 22 = 4
Rule: factor each number into primes; the GCF multiplies every prime the numbers share, each at its lowest power.
See Also
- Least Common Multiple - Find the Least Common Multiple (LCM) of two numbers
- Greatest Common Factor of 3 Numbers - Find the Greatest Common Factor (GCF) of three numbers
- Least Common Multiple of 3 Numbers - Find the Least Common Multiple (LCM) of three numbers
FAQ
What is the greatest common factor of two numbers?
It is the largest positive integer that divides both numbers with no remainder. The same value is also called the greatest common divisor (GCD) and the highest common factor (HCF) — three names for one number. For 12 and 16 it is 4.
How do you find the GCF by prime factorization?
Split both numbers into prime factors and multiply the primes they share, each taken as many times as it appears in both factorizations. 12 = 2 × 2 × 3 and 16 = 2 × 2 × 2 × 2 share 2 × 2, so the GCF is 4.
What is the Euclidean algorithm for the GCF?
Euclid described it in the Elements around 300 BC: divide the larger number by the smaller one, then replace the pair with the smaller number and the remainder, until the remainder is 0. For 16 and 12 that is 16 mod 12 = 4 and then 12 mod 4 = 0, so the GCF is 4. It never factorizes anything, which is why it stays fast on numbers far too large to factor.