GCF Calculator
Calculate the Greatest Common Factor (GCF / GCD) of integers.
The Euclidean algorithm, and why it is fast
The greatest common factor is the largest integer dividing two numbers exactly. Listing every factor of both and picking the largest shared one works, and becomes impractical quickly. Prime factorisation is better: take each shared prime at its lowest power, so 48 = 2⁴ × 3 and60 = 2² × 3 × 5 share 2² × 3 = 12.
The Euclidean algorithm is faster than either and needs no factorisation at all. Divide the larger by the smaller, keep the remainder, repeat with the smaller and that remainder, and stop when the remainder hits zero — the last non-zero remainder is the GCF. For 48 and 60: 60 ÷ 48 leaves 12, then 48 ÷ 12 leaves 0, so the answer is 12. It finishes in a handful of steps even for enormous numbers, which is why it is still in use after two millennia.
GCF is what reduces a fraction to lowest terms in one step: dividing both parts of48/60 by 12 gives 4/5 immediately. It pairs with the LCM through the identity GCF(a,b) × LCM(a,b) = a × b, so finding either one gives you the other for free. Numbers with a GCF of 1 are called coprime.
Frequently Asked Questions
What is the Greatest Common Factor (GCF)?
The GCF (also known as GCD) of two or more non-zero integers is the largest positive integer that divides each of the numbers without a remainder.
What is the Euclidean Algorithm?
The Euclidean algorithm computes the GCF by repeatedly finding remainders: gcd(a, b) = gcd(b, a mod b) until remainder is 0.
How do I find the greatest common factor?
The Euclidean algorithm is fastest: divide the larger number by the smaller, replace the larger with the remainder, and repeat until the remainder is zero - the last non-zero remainder is the GCF. For 48 and 18: 48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, so the GCF is 6.
How are GCF and LCM related?
For any two positive integers, GCF x LCM = a x b. So knowing one gives the other immediately: with 48 and 18, GCF 6 means LCM is 864/6 = 144. The identity does not extend directly to three or more numbers.