GCD Calculator

What is the greatest common divisor?

The greatest common divisor, or GCD, is the largest whole number that divides two integers without leaving a remainder. You will also see it called the greatest common factor (GCF) or highest common factor (HCF), but they all mean the same thing. For example, the GCD of 12 and 18 is 6, because 6 is the biggest number that fits evenly into both.

It shows up most often when you simplify fractions, since dividing the top and bottom by their GCD reduces a fraction to its lowest terms.

How the calculator finds it

Behind the scenes it uses the Euclidean algorithm, which is far faster than checking every possible factor. The idea is simple: keep replacing the larger number with the remainder of dividing the two, and stop when the remainder hits zero. The last non-zero value is the GCD.

How to use this calculator

1. Enter the first number, \(a\).
2. Enter the second number, \(b\).
3. Click calculate to find \(\gcd(a,b)\).
4. Use the result to simplify fractions or compare factors.

The formula explained

The formula \(\gcd(a,b)=\gcd(b, a \bmod b)\) is the Euclidean algorithm. It keeps replacing the pair with a smaller remainder until the remainder is 0, and the last nonzero value is the GCD.

• a = the first number
• b = the second number
• \(a \bmod b\) = the remainder when \(a\) is divided by \(b\)

Step by step method

1. List the divisors of both numbers or use repeated division.
2. Find the largest number that appears in both divisor lists.
3. Or use the Euclidean algorithm by dividing and taking remainders until the remainder is 0.

Worked example

Problem. Find the GCD of 48 and 18.

1. Divide 48 by 18, which gives a remainder of 12, so \(\gcd(48,18)=\gcd(18,12)\).
2. Divide 18 by 12, which gives a remainder of 6, so \(\gcd(18,12) = \gcd(12,6)\).
3. Divide 12 by 6, which gives a remainder of 0, so the GCD is 6.

Tips and common mistakes

• If one number is 0, the GCD is the other number, as long as it is not 0.
• Make sure you are finding the greatest common divisor, not the least common multiple.

Frequently asked questions