GCD Calculator

About this GCD Calculator

The GCD Calculator finds the largest positive integer that divides two integers without leaving a remainder. The same value is also called the greatest common factor or highest common factor in many textbooks.

The greatest common divisor is the foundation for simplifying fractions to lowest terms, and it also shows up in scheduling problems, cryptography key generation and music theory rhythm calculations, making it one of the more quietly useful concepts in basic number theory.

For related tasks, try LCM Calculator, Prime Number Checker or Fraction Calculator.

How the calculation works

The tool uses the Euclidean algorithm, repeatedly replacing the larger relationship with a remainder until the remainder reaches zero. The last non-zero divisor is the GCD.

How to use it

1. Enter the first integer.
2. Enter the second integer.
3. Calculate to find their greatest common divisor.

Practical example

The GCD of 48 and 18 is 6 because 6 is the largest integer that divides both values exactly.

The GCD of 48 and 18 is 6, found using the Euclidean algorithm (48 = 2x18 + 12, then 18 = 1x12 + 6, then 12 = 2x6 + 0), which also means 48/18 simplifies to 8/3.

Things to double-check

The GCD of two numbers is always at least 1, and when the GCD equals 1 the two numbers are called coprime (or relatively prime), meaning they share no common factors other than 1, which is different from either number being prime itself.

How the greatest common divisor is found

The Euclidean algorithm repeatedly divides and keeps the remainder. For 84 and 36, 84 divided by 36 leaves 12, then 36 divided by 12 leaves 0, so the greatest common divisor is 12. Another method uses prime factors: 84 is 2 times 2 times 3 times 7 and 36 is 2 times 2 times 3 times 3, so the common factors multiply to 2 times 2 times 3, which is 12. Both methods give the same answer, and the Euclidean method is much faster for large numbers.

Practical uses

The GCD simplifies fractions: 84/36 divides by 12 to give 7/3. It also solves sharing and tiling problems. A floor 84 by 36 units can be covered with square tiles whose side is at most 12 units without cutting, and 84 apples and 36 oranges can be shared into at most 12 identical baskets, each holding 7 apples and 3 oranges. Whenever you must split things into equal groups with no leftovers, the GCD tells you the largest group size that works.

Coprime numbers

Two numbers whose GCD is 1 are called coprime or relatively prime. For example 14 and 15 are coprime even though neither is prime. Coprime pairs matter in fractions, because a fraction is in lowest terms exactly when its numerator and denominator are coprime, and in cryptography, where coprime numbers are used to build keys. If the calculator returns 1, the numbers share no common factor other than 1.

Links to the LCM

The GCD and least common multiple are connected: their product equals the product of the two numbers. For 84 and 36, the GCD is 12 and the LCM is 252, and 12 times 252 is 3,024, which equals 84 times 36. This gives a quick way to find the LCM once you know the GCD, and a check on both results. The GCD of a number and zero is the number itself, and negative numbers are treated by their absolute values.

Three numbers and ratios

The GCD of more than two numbers is found step by step. For 48, 72 and 120, the GCD of 48 and 72 is 24, and the GCD of 24 and 120 is 24, so all three share a greatest divisor of 24. Dividing each by 24 gives the simplest ratio, 2 to 3 to 5. This is how you reduce a mixture or a share of costs to its smallest whole numbers. If the result is 1, the numbers have no common divisor beyond 1. The same method helps you pack different items into identical boxes with nothing left over.

Worked example with the Euclidean algorithm

Take the numbers 1071 and 462, a classic example. Divide 1071 by 462: it goes twice with a remainder of 147, since 2 times 462 is 924. Next divide 462 by 147: it goes three times with a remainder of 21. Then divide 147 by 21: it goes exactly 7 times with no remainder. The last non-zero remainder, 21, is the greatest common divisor. The method works because the common divisors of two numbers are the same as those of the smaller number and the remainder. Each step makes the numbers smaller, so the process always ends quickly, even for numbers with many digits.

Simplifying fractions and ratios

Once you know the GCD, simplifying is easy. The fraction 462/1071 has a GCD of 21, so it simplifies to 22/51 by dividing the top and bottom by 21. The same works for ratios: the ratio 462 to 1071 is 22 to 51. If the GCD is 1, the fraction is already in lowest terms. For a fraction with large numbers, finding the GCD with the algorithm is much faster than guessing small divisors one by one. Many teachers ask for answers in lowest terms, so a quick check with the GCD makes sure that your final fraction is fully simplified.

Real-world sharing problems

The GCD answers questions about equal groups. Two ribbons of 84 cm and 60 cm are to be cut into equal pieces with no waste. The GCD is 12, so the longest possible piece is 12 cm, giving 7 pieces from the first ribbon and 5 from the second. A class with 48 boys and 36 girls can be split into teams with the same mix: the GCD is 12, so there can be 12 teams, each with 4 boys and 3 girls. Whenever you have two quantities and want identical groups with nothing left over, the greatest common divisor gives the largest number of identical groups.

GCD in programming and cryptography

The Euclidean algorithm is one of the oldest algorithms still in everyday use. It is efficient, because the number of steps grows with the number of digits, not with the size of the numbers. Programmers use it to reduce fractions, to compute the least common multiple and to work out modular arithmetic. In cryptography, the RSA system relies on choosing numbers that are coprime, meaning their GCD is 1, and on an extended form of the algorithm to find modular inverses. Understanding this small algorithm opens the door to a lot of mathematics and computer science.

Key terms explained

A divisor of a number divides it exactly. A common divisor divides two or more numbers, and the greatest common divisor, also called the highest common factor, is the largest of them. Coprime numbers have a greatest common divisor of 1. Prime factorisation writes a number as a product of primes. The Euclidean algorithm finds the divisor by repeated division with remainder, and the least common multiple is the smallest number that all the inputs divide into.

Rules of thumb and quick checks

The greatest common divisor of a and b equals that of b and the remainder of a divided by b. The product of the greatest common divisor and the least common multiple equals the product of the two numbers. If one number divides the other, the answer is the smaller number, and consecutive whole numbers are always coprime. As an example, the divisor of 100 and 75 is 25. If the tool returns 1, the fraction made from the two numbers is already in lowest terms.

Frequently asked questions