Greatest Common Divisor (GCD) Calculator

1. Enter two or more whole numbers. Commas, spaces or line breaks all work, so you can paste a column from a spreadsheet.
2. Confirm the count. "Numbers read" shows how many values were found and whether any signs or zeros were handled.
3. Read the GCD and the working. Each Euclidean division step, the prime factors and the numbers divided by the GCD appear under the result.

The greatest common divisor of a set of whole numbers is the largest positive whole number that divides each of them exactly. The NIST Dictionary of Algorithms and Data Structures gives the example GCD(30, 42) = 6: 6 divides both 30 and 42, and no larger number does.

The same number goes by several names. Algebra books usually say greatest common factor (GCF); British and Commonwealth schools say highest common factor (HCF). All three names mean the same value.

A divisor (or factor) of a number divides it with remainder 0. The divisors of 30 are 1, 2, 3, 5, 6, 10, 15 and 30; the divisors of 42 are 1, 2, 3, 6, 7, 14, 21 and 42. The common divisors are 1, 2, 3 and 6, and the greatest is 6.

When the GCD is 1, the numbers are called coprime or relatively prime. 35 and 64 are coprime even though neither is prime. The GCD is the partner of the least common multiple, which the LCM calculator works out in full.

The calculator runs the Euclidean algorithm for the answer and confirms it with prime factorization.

1. Divide the larger number by the smaller and note the remainder: 180 = 3 x 48 + 36.
2. Replace the pair with the smaller number and the remainder: now find GCD(48, 36).
3. Repeat: 48 = 1 x 36 + 12, then 36 = 3 x 12 + 0.
4. Stop at remainder 0. The last nonzero remainder, 12, is the GCD.
5. Cross-check with primes. 48 = 2⁴ x 3 and 180 = 2² x 3² x 5. The shared primes at their lowest powers are 2² x 3 = 12.

The method works because any number that divides a and b also divides the remainder a - q x b, so each step keeps the same common divisors while the numbers shrink. NIST lists the running time as O((log a)(log b)) bit operations, which is why the tool handles numbers up to a trillion instantly. For three or more numbers, it applies the rule one pair at a time.

Here is one pair worked both ways, the way a teacher might ask for it.

Euclidean Algorithm

The last nonzero remainder is 21, so GCD(1,071, 462) = 21.

Prime Factorization

1,071 = 3² x 7 x 17 and 462 = 2 x 3 x 7 x 11. The primes in both are 3 (lowest power 3¹) and 7, so the GCD is 3 x 7 = 21. Same answer.

What the Result Gives You

Dividing by 21 reduces the fraction 462/1,071 to 22/51. The LCM follows from the GCD: 1,071 x 462 / 21 = 23,562.

A three-number case: for 24, 60 and 84, GCD(24, 60) = 12 and then GCD(12, 84) = 12, so the GCD of all three is 12. Dividing gives the ratio 2 : 5 : 7.

Shared primes, special values and the way the numbers relate to each other decide the GCD.

Shared Prime Factors

The GCD is built only from primes that every number contains. 150, 225 and 375 all contain 3 x 5², so their GCD is 75.

One Number Divides the Others

If the smallest number divides all the rest, it is the GCD. GCD(12, 84) = 12, found in one Euclidean step: 84 = 7 x 12 + 0.

Consecutive Whole Numbers

Two numbers next to each other, such as 64 and 65, always have GCD 1, because any common divisor would also divide their difference, 1.

Zero in the List

Every number divides 0, so GCD(a, 0) = a. The tool follows that rule and ignores zeros; a list of only zeros returns 0 by convention with a warning.

Negative Numbers

-48 has the same divisors as 48, so signs are dropped and the GCD is reported as a positive number.

All three methods give the same GCD; they differ in speed and in what they show.

GCD vs LCM

The GCD takes each shared prime at its lowest power; the LCM takes every prime at its highest power. For two numbers they are linked by GCD x LCM = a x b, so 12 x 720 = 48 x 180 = 8,640. University of Maryland notes prove this for any two positive integers.

Reducing Fractions

Divide the top and bottom by their GCD to reach lowest terms in one step: 84/126 has GCD 42, so it reduces to 2/3. The fraction calculator does this after every operation.

Simplifying Ratios

A 24 : 60 : 84 mix divides by 12 to give 2 : 5 : 7. The ratio calculator scales the result to any total.

Equal Groups and Square Tiles

A 48 by 180 inch floor can be covered with no cutting by square tiles up to GCD(48, 180) = 12 inches on a side: 4 rows of 15, or 60 tiles.

Sharing Without Leftovers

With 24 pencils and 60 erasers, the most identical kits you can make is 12, each with 2 pencils and 5 erasers.

1. Mixing Up GCD and LCM

The GCD is never larger than the smallest nonzero number; the LCM is never smaller than the largest. If your "GCD" of 48 and 180 is 720, you found the LCM.

2. Taking the Highest Powers

For the GCD use the lowest power of each shared prime. 2⁴ from 48 would give 48, which does not divide 180.

3. Including a Prime That Is Not in Every Number

The 5 in 180 is not in 48, so it stays out of the GCD.

4. Stopping the Euclidean Algorithm Early

Keep going until the remainder is 0. The answer is the last nonzero remainder, not the last quotient.

5. Assuming Two Composite Numbers Share a Factor

35 = 5 x 7 and 64 = 2⁶ have no prime in common, so their GCD is 1.

6. Typing Thousands Separators

In the input box, 1,071 is read as two numbers, 1 and 71. Type 1071 instead.

Results are exact: the Euclidean steps use whole-number division, and every intermediate value stays within the range JavaScript stores exactly.

To break any single number into primes in more detail, the prime factorization calculator shows the factor tree.

It is 6. 18 = 1 x 12 + 6 and 12 = 2 x 6 + 0, so the last nonzero remainder is 6.

Yes. Greatest common divisor, greatest common factor and highest common factor are three names for the same number.

It is 1 when the primes are different, because a prime has no divisors other than 1 and itself. GCD(13, 17) = 1.

It is the number itself. Every whole number divides 0, so GCD(15, 0) = 15.

No. The GCD must divide the smallest nonzero number, so it can be at most that number.

Find the GCD of the first two, then the GCD of that result with the third. For 24, 60 and 84: GCD(24, 60) = 12 and GCD(12, 84) = 12.

Divide the numerator and denominator by their GCD. 84/126 has GCD 42, so it simplifies to 2/3.

For two positive numbers, GCD x LCM equals their product. For 48 and 180, 12 x 720 = 8,640 = 48 x 180.

The numbers are coprime: they share no factor except 1. Any fraction made from them, such as 35/64, is already in lowest terms.

By the usual convention, no. -12 and 18 have the same divisors as 12 and 18, and the GCD is reported as 6.

No. The calculation runs in your browser, and Save keeps a copy only in your own browser storage.

• Greatest common divisor definition, GCD(30, 42) = 6 (NIST Dictionary of Algorithms and Data Structures).
• Euclid's algorithm and its running time (NIST Dictionary of Algorithms and Data Structures).
• Finding the greatest common factor by prime factors (OpenStax Elementary Algebra 2e, section 7.1).
• Prime factorization of whole numbers (OpenStax Prealgebra 2e, section 2.5).
• Proof that LCM(a, b) x GCD(a, b) = ab (University of Maryland, Department of Mathematics).