GCF Calculator
By Talcart · Last updated July 10, 2026
GCF Calculator
A GCF calculator finds the largest integer that divides every number you enter with no remainder - the GCF of 12 and 18 is 6, and the GCF of 48 and 36 is 12. It accepts two or more integers, shows the Euclidean algorithm steps, and is the standard tool for reducing fractions and ratios to simplest form.
Key facts
- The Euclidean algorithm appears in Book VII of Euclid's Elements (c. 300 BC), making it one of the oldest algorithms still in everyday use.
- Lame proved in 1844 that the Euclidean algorithm takes at most about five iterations per decimal digit of the smaller number - and the worst case is consecutive Fibonacci numbers.
- For any two positive integers, gcf(a, b) x lcm(a, b) = a x b.
What is the GCF Calculator?
The greatest common factor (GCF) of a set of integers is the largest positive integer that divides each of them exactly. It is also called the greatest common divisor (GCD) or highest common factor (HCF) - three names for the same number. The factors of 12 are 1, 2, 3, 4, 6, 12 and the factors of 18 are 1, 2, 3, 6, 9, 18; the largest shared factor is 6. Numbers with a GCF of 1 are called coprime. The GCF is the key to reducing fractions and to much of elementary number theory.
How does the GCF Calculator work?
The calculator uses the Euclidean algorithm: replace the pair (a, b) with (b, a mod b) until the remainder is 0; the last nonzero value is the GCF. For 48 and 36: 48 mod 36 = 12, then 36 mod 12 = 0, so gcf(48, 36) = 12. The algorithm runs in O(log min(a, b)) steps, so even ten-digit inputs finish instantly - far faster than listing factors or building prime factorizations. For more than two numbers it folds pairwise: gcf(a, b, c) = gcf(gcf(a, b), c).
What is the GCF Calculator formula?
- mod – remainder operator
Worked GCF examples
| Numbers | GCF | Note |
|---|---|---|
| 12, 18 | 6 | Shared factors: 1, 2, 3, 6 |
| 48, 36 | 12 | Euclid: 48 mod 36 = 12; 36 mod 12 = 0 |
| 8, 20 | 4 | Both divisible by 4, not by 8 |
| 15, 28 | 1 | Coprime - no shared prime factor |
| 8, 24 | 8 | GCF equals an input: 8 divides 24 |
| 17, 51 | 17 | 51 = 3 x 17 |
| 100, 75 | 25 | Both are multiples of 25 |
| 24, 36, 60 | 12 | Pairwise: gcf(24, 36) = 12; gcf(12, 60) = 12 |
How do you use the GCF Calculator?
- Enter two or more integers.
- Read the GCF.
Worked example
| Scenario | gcf(48, 36) |
| Calculation | 48 mod 36 = 12; 36 mod 12 = 0 |
| Result | GCF = 12. |
Common use cases
Tips & best practices
Prime factorisation is intuitive but slow for big numbers — Euclidean is much faster.
Frequently asked questions
The GCF of 12 and 18 is 6. The factors of 12 are 1, 2, 3, 4, 6, and 12; the factors of 18 are 1, 2, 3, 6, 9, and 18. The largest number on both lists is 6. Equivalently, by the Euclidean algorithm: 18 mod 12 = 6, then 12 mod 6 = 0, confirming the answer.
It repeatedly replaces the larger number with the remainder of dividing the two, because any common divisor of a and b also divides a mod b. For gcf(48, 36): 48 mod 36 = 12, then 36 mod 12 = 0, so the GCF is 12. The process always terminates because remainders strictly shrink, and it needs only O(log n) steps.
The GCF of two different primes is always 1, because a prime's only factors are 1 and itself, and two distinct primes share only the factor 1. For example, gcf(7, 13) = 1. The exception is identical primes: gcf(7, 7) = 7. Pairs with GCF 1 are called coprime or relatively prime.
Yes - the GCF equals the smaller number exactly when it divides the larger one. For example, gcf(8, 24) = 8 because 24 = 3 x 8, and gcf(17, 51) = 17 because 51 = 3 x 17. The GCF can never exceed the smallest input, since a divisor of a number cannot be larger than the number itself.
For any two positive integers, GCF x LCM = a x b. Take 4 and 6: gcf = 2 and lcm = 12, and indeed 2 x 12 = 24 = 4 x 6. This identity gives the fastest way to compute an LCM - find the GCF with the Euclidean algorithm, then divide the product by it. Note the identity holds for exactly two numbers, not three or more.
Yes - greatest common factor (GCF), greatest common divisor (GCD), and highest common factor (HCF) are three names for the identical concept. GCF dominates in American school textbooks, HCF in British and Indian curricula, and GCD in university mathematics and computer science. Any calculator or formula for one applies unchanged to the others.