GCD, GCF and HCF Calculator
Enter numbers in the first tab, then come back here for the full working.
No data yet. Enter at least two numbers in the GCD / GCF / HCF tab.
What is the GCD (greatest common divisor)?
The greatest common divisor of a set of integers is the biggest positive integer that goes into every one of them evenly. "Evenly" means the division leaves a remainder of 0. You will see it written GCD(a, b), gcd(a, b), or just (a, b) in number theory books.
Take 12 and 18. The factors of 12 are 1, 2, 3, 4, 6 and 12. The factors of 18 are 1, 2, 3, 6, 9 and 18. They share 1, 2, 3 and 6, and the largest of those is 6. So GCD(12, 18) = 6.
| Pair | Common factors | GCD |
|---|---|---|
| 12 and 18 | 1, 2, 3, 6 | 6 |
| 8 and 9 | 1 | 1 |
| 100 and 75 | 1, 5, 25 | 25 |
The middle row has a GCD of 1. Pairs like that are called coprime, and they get their own section below.
Signs do not matter, because divisors ignore them: GCD(−12, 18) = GCD(12, 18) = 6. Zero is the odd case. Every integer divides 0, so GCD(a, 0) = |a|. GCD(0, 0) is undefined because zero has no largest divisor. The calculator above follows these conventions and will tell you if you enter two zeros.
If you work with counts and proportions, this is one of the small number tools you reach for often. The rest of them live in the calculators section, and the broader theory sits under statistics and probability.
GCD vs GCF vs HCF: are they the same?
Yes. It is one calculation with three labels. American schools say GCF. University math and computer science say GCD. The UK, India, Australia and most Commonwealth countries say HCF. Older books sometimes use "greatest common measure." Whichever you searched for, this calculator finds it.
How to find the GCD: three methods
All three methods below use the pair 48 and 36, so you can compare them directly. Each one lands on 12.
Method 1: listing factors
- Factors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
- Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.
- Common factors: 1, 2, 3, 4, 6, 12.
- The largest is 12, so GCD(48, 36) = 12.
This works for small numbers and falls apart quickly for large ones. If you like to see factor overlap drawn out, our Venn diagram maker can show the two factor lists as overlapping circles.
Method 2: prime factorization
Break each number into primes: 48 = 24 × 3 and 36 = 22 × 32. Then keep each shared prime at its lowest exponent. The prime 2 appears as 24 and 22, so take 22. The prime 3 appears as 31 and 32, so take 31.
It is systematic, and it is easy to check by hand for numbers up to a few hundred. The catch is that factoring a large number is slow, which is why software does not use this method for big inputs.
Method 3: the Euclidean algorithm
Euclid described this in the Elements around 300 BCE, and it is still the standard way to compute a GCD. It rests on one fact: any number that divides both a and b also divides the remainder when a is divided by b. So GCD(a, b) = GCD(b, a mod b), and the numbers shrink at every step until the remainder hits 0.
| Step | Division | Quotient | Remainder |
|---|---|---|---|
| 1 | 48 = 1 × 36 + 12 | 1 | 12 |
| 2 | 36 = 3 × 12 + 0 | 3 | 0 |
The remainder reached 0 at step 2, so the answer is the last nonzero remainder, 12. A longer case, GCD(252, 105):
| Step | Division | Quotient | Remainder |
|---|---|---|---|
| 1 | 252 = 2 × 105 + 42 | 2 | 42 |
| 2 | 105 = 2 × 42 + 21 | 2 | 21 |
| 3 | 42 = 2 × 21 + 0 | 2 | 0 |
So GCD(252, 105) = 21. Each row takes the divisor and the remainder from the row above, so nothing appears out of nowhere.
The algorithm is fast. In 1844 Gabriel Lamé proved that the number of division steps never exceeds five times the number of digits in the smaller input. Two 10-digit numbers need at most 50 steps. Testing every integer up to the smaller number could take 10 billion checks. The slowest inputs are consecutive Fibonacci numbers: GCD(89, 55) takes nine steps.
GCD of more than two numbers
Work in pairs: GCD(a, b, c) = GCD(GCD(a, b), c). For 12, 18 and 24, start with GCD(12, 18) = 6, then take GCD(6, 24) = 6. The answer is 6. The calculator does the same chain for up to 10 numbers, and the step-by-step tab shows each link.
GCD and LCM: the key relationship
For two positive integers, GCD(a, b) × LCM(a, b) = a × b. Rearranged, LCM(a, b) = (a × b) / GCD(a, b). With 12 and 18: GCD is 6, so LCM = (12 × 18) / 6 = 216 / 6 = 36.
The two are partners. The GCD reduces fractions to lowest terms, and the LCM finds a common denominator when you add them. When two numbers are coprime, the LCM is just their product.
One warning. The identity does not carry over to three numbers. For 4, 6 and 10 the GCD is 2 and the LCM is 60, so GCD × LCM = 120, while 4 × 6 × 10 = 240. The same idea appears in counting: simplifying a result like C(10, 4) = 10! / (4! × 6!) is a GCD job, which you can check with the combination calculator or read about in permutations and combinations.
Coprime numbers: what GCD = 1 means
Two integers are coprime, or relatively prime, when their GCD is 1. They share no factor except 1. Being coprime is a relationship between two numbers; it does not mean either number is prime. For example, 8 and 9 are coprime (GCD = 1), but neither is prime: 8 = 23 and 9 = 32.
- GCD(14, 15) = 1. Here 14 = 2 × 7 and 15 = 3 × 5, with no prime in common.
- GCD(100, 101) = 1. Consecutive integers are always coprime.
- GCD(7, 11) = 1. Two different primes are always coprime.
The consecutive-integer rule has a short proof. A common divisor of n and n + 1 must also divide their difference, which is 1. And a note on 1 itself: it is not a prime number (a prime has exactly two divisors), yet GCD(1, n) = 1 for every n.
With three or more numbers, "coprime" can mean two things. The set 6, 10, 15 has an overall GCD of 1, but every pair shares a factor: GCD(6, 10) = 2, GCD(6, 15) = 3, GCD(10, 15) = 5. Such a set is coprime as a whole but not pairwise coprime. The calculator reports both.
Real-world applications of GCD
Simplifying fractions
Divide the numerator and the denominator by their GCD. For 24/36, GCD(24, 36) = 12, so the fraction becomes 2/3. In probability this is routine. Roll two fair dice and the chance of a sum of 4 is 3/36, which reduces to 1/12 after dividing by 3. A survey where 15 of 40 students chose a topic gives a relative frequency of 15/40 = 3/8. For the percentage version, try the percentage calculator, and for event odds see the probability calculator.
Simplifying ratios and proportions
A trial has 24 responders and 36 non-responders. GCD(24, 36) = 12, so the ratio of responders to non-responders is 2:3. Same trick for any pair of counts in a table.
Dividing items into equal groups
You have 48 apples and 36 oranges and want identical baskets with nothing left over. GCD(48, 36) = 12, so you can fill 12 baskets, each with 4 apples and 3 oranges. Twelve is the most baskets possible.
Cryptography (RSA encryption)
RSA key generation needs a public exponent e that is coprime to φ(n). The textbook example uses n = 3233 (from the primes 61 and 53), so φ(n) = 3120, and e = 17. The Euclidean algorithm confirms it: 3120 = 183 × 17 + 9, then 17 = 1 × 9 + 8, then 9 = 1 × 8 + 1, then 8 = 8 × 1 + 0. The GCD is 1. Running the same steps backward, the extended Euclidean algorithm gives the private exponent d = 2753. Secure web connections lean on this arithmetic every day.
Frequently asked questions
The GCD (greatest common divisor) of two or more integers is the largest positive integer that divides each of them without a remainder. For example, GCD(12, 18) = 6, because 6 is the largest number that divides both 12 and 18 exactly. The GCD is also called the GCF (greatest common factor) or HCF (highest common factor). All three names refer to the same concept.
GCD (greatest common divisor), GCF (greatest common factor), and HCF (highest common factor) are three names for the same mathematical concept. GCF is most common in US school mathematics, GCD in advanced mathematics and computer science, and HCF in the UK, India, and other Commonwealth countries. This calculator computes all three.
To find GCD(a, b): (1) Divide the larger number by the smaller and find the remainder. (2) Replace the larger number with the smaller, and the smaller with the remainder. (3) Repeat until the remainder is 0. (4) The last nonzero remainder is the GCD. Example, GCD(48, 18): 48 ÷ 18 = 2 remainder 12, then 18 ÷ 12 = 1 remainder 6, then 12 ÷ 6 = 2 remainder 0. GCD = 6.
Two integers are coprime (also called relatively prime) if their GCD equals 1, so they share no common factors other than 1. For example, GCD(8, 9) = 1, so 8 and 9 are coprime. Coprime does not mean prime: 8 and 9 are both composite numbers but are still coprime to each other. Any two consecutive integers are always coprime.
For any two positive integers a and b: GCD(a, b) × LCM(a, b) = a × b. This means once you know the GCD, you can find the LCM without listing multiples: LCM(a, b) = (a × b) / GCD(a, b). Example: GCD(12, 18) = 6, so LCM(12, 18) = (12 × 18) / 6 = 36.
GCD has several practical uses. (1) Simplifying fractions: divide numerator and denominator by their GCD to reach lowest terms (24/36 ÷ 12 = 2/3). (2) Dividing equally: find the largest equal group size from two quantities with no leftovers. (3) Simplifying ratios: reduce 24:36 to 2:3 by dividing by GCD 12. (4) Cryptography: the extended Euclidean algorithm underpins RSA public-key encryption. (5) Computer science: GCD appears in modular arithmetic and algorithm design.
Want more tools like this one? The full set is on the statistics calculators page. If GCD came up while simplifying probabilities, the basic probability guide is a good next stop, and the statistics cheat sheet keeps the common formulas on one page.
Related calculators and guides
Sources and further reading
- Euclid. Elements, Book VII, Propositions 1 and 2 (the Euclidean algorithm). Clark University edition
- Wolfram MathWorld. Greatest Common Divisor. mathworld.wolfram.com
- Wikipedia. Euclidean algorithm, including Lamé's theorem on step counts. en.wikipedia.org
- Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Section 4.5.2.
- Rivest, R., Shamir, A. & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120–126.