Euclid's algorithm in plain terms
The greatest common factor is the largest whole number that divides every input with no remainder. Listing all factors of each number and comparing them works, but it is slow for large values.
Instead this calculator uses Euclid's algorithm: divide the larger number by the smaller, keep the remainder, and repeat with the smaller number and that remainder. When the remainder reaches zero, the last nonzero value is the GCF. For three numbers it finds the GCF of the first two, then the GCF of that result with the third.
Reading and using the result
A GCF of 1 means the numbers are coprime, sharing no common factor beyond 1. A larger GCF tells you the biggest chunk size that divides all the inputs evenly.
The most common use is reducing a fraction: divide the numerator and denominator by their GCF to get lowest terms. For example, the GCF of 48 and 36 is 12, so 48/36 reduces to 4/3.
Practical uses
Finding the GCF shows up in many real splitting-and-sharing problems.
- Dividing items into the largest possible equal groups with nothing left over.
- Simplifying ratios and fractions to their cleanest form.
- Figuring out the largest tile or unit size that fits two dimensions exactly.
- It pairs with the least common multiple: GCF × LCM equals the product of the two numbers.
Common mistakes
Do not confuse the GCF with the LCM. The greatest common factor is never larger than the smallest input, while the least common multiple is never smaller than the largest input.
Inputs must be whole numbers, and the sign does not matter because the algorithm works with absolute values. Leave the third field at 0 when you only want the GCF of two numbers.
Formula
gcd(a, b) via Euclid; gcd(a, b, c) = gcd(gcd(a, b), c)Frequently asked questions
- What is the difference between GCF and GCD?
- None — greatest common factor and greatest common divisor are two names for the same value.