Greatest Common Factor (GCF) Calculator
Find the greatest common factor (also called the greatest common divisor, or GCD) of two or more numbers, with prime factorization and the step-by-step Euclidean algorithm shown.
Greatest Common Factor
6
Result
GCF(18, 24, 36) = 6
What is the Greatest Common Factor?
The greatest common factor (GCF), also called the greatest common divisor (GCD), of two or more non-zero integers is the largest positive integer that divides evenly into all of them. For example, GCF(32, 256) = 32, since 32 divides evenly into both numbers and no larger number does.
GCF is used to simplify fractions to lowest terms, split quantities into equal-sized groups (like dividing students into the largest possible equal teams), and as a building block for other number theory problems, including finding the LCM of a set of numbers.
Prime Factorization of Each Number
The GCF equals the product of every prime factor shared by all the numbers, taken at its lowest shared power.
| Number | Prime Factorization |
|---|---|
| 18 | 18 = 2 × 3 × 3 |
| 24 | 24 = 2 × 2 × 2 × 3 |
| 36 | 36 = 2 × 2 × 3 × 3 |
Step-by-Step: The Euclidean Algorithm
Each row divides the larger number by the smaller and keeps the remainder, repeating until the remainder reaches zero — at that point the last non-zero remainder is the GCF for that pair.
| a | b | Quotient | Remainder (a mod b) |
|---|---|---|---|
| 18 | 24 | 0 | 18 |
| 24 | 18 | 1 | 6 |
| 18 | 6 | 3 | 0 |
| 6 | 36 | 0 | 6 |
| 36 | 6 | 6 | 0 |
Two Ways to Find the GCF
Prime factorization — break each number into its prime factors, then multiply together every prime factor shared by all the numbers, at its lowest shared power. For example: 16 = 2×2×2×2, 88 = 2×2×2×11, 104 = 2×2×2×13 — all three share three factors of 2, so GCF(16, 88, 104) = 2×2×2 = 8. This method is easy to follow but only practical for relatively small numbers, since factoring large numbers by hand gets difficult fast.
Euclidean algorithm — repeatedly divide the larger number by the smaller and keep the remainder, replacing the larger number with the smaller and the smaller with the remainder, until the remainder reaches zero. The last non-zero remainder is the GCF. This method works efficiently even for very large numbers, since it needs relatively few steps regardless of how big the inputs are — the table above shows this method applied to your numbers.
Why the Euclidean Algorithm Works
The method relies on a simple fact: if a number divides evenly into both a and b, it also divides evenly into their difference (and therefore their remainder after division). So GCF(a, b) is always equal to GCF(b, a mod b) — repeating this shrinks the numbers quickly until one of them hits zero, at which point the other one is the answer. This is one of the oldest known algorithms in mathematics, dating back over 2,000 years to Euclid's "Elements."
Example — Your Current Inputs
GCF(18, 24, 36) = 6
Additional Example — Large Numbers
Find GCF(268442, 178296) using the Euclidean algorithm: 268442 ÷ 178296 leaves a remainder of 90146; 178296 ÷ 90146 leaves 88150; 90146 ÷ 88150 leaves 1996; continuing this process eventually reaches a remainder of 0, and the GCF turns out to be 2 — even though both starting numbers are large and share no obvious small common factor at a glance, the algorithm finds the answer in only a handful of steps.
About This Calculator
- Numbers
- Enter two or more positive whole numbers, separated by commas, spaces, or new lines. The calculator finds the GCF across the entire list, folding numbers in one at a time using the Euclidean algorithm.
Frequently Asked Questions
What is the GCF used for?
The most common use is reducing a fraction to its simplest (lowest) terms — divide both the numerator and denominator by their GCF. It's also used to split a quantity into the largest possible equal-sized groups, and as a step in computing the LCM of a set of numbers.
What is the GCF of two numbers that share no common factors?
If two numbers share no factors other than 1 (called "coprime" or "relatively prime"), their GCF is 1. For example, GCF(9, 28) = 1, even though neither number is prime itself.
Can the GCF ever be larger than the smallest input number?
No — the GCF can never exceed the smallest number in the list, since a factor of every number must also be a factor of (and therefore no larger than) the smallest one. It equals the smallest number exactly when that number divides evenly into all the others (for example, GCF(6, 12, 18) = 6).
Is the Euclidean algorithm faster than prime factorization?
For large numbers, yes, significantly. Prime factorization requires finding all prime factors of every number, which gets slow as numbers grow large. The Euclidean algorithm only needs a small number of division steps regardless of the size of the inputs, which is why it's the standard method used in computer implementations of GCF.