GCD calculator
Enter two whole numbers and see their greatest common divisor, with every step of Euclid's algorithm. You also get the least common multiple and whether the numbers are coprime.
Fill in the fields; the answer appears here straight away.
How it's worked out
How it works
-
Enter the values
Type the numbers or the formula. Decimals may use a point or a comma. No idea? Click Fill in an example.
-
Instant answer
The answer appears as you type, with the most important intermediate values.
-
See the working
Under "How it's worked out" you see the steps, handy for checking your own calculation.
What is the GCD?
The greatest common divisor (GCD), also called the highest common factor (HCF), is the largest number that divides both numbers without a remainder. The GCD of 84 and 126 is 42. You use it to simplify fractions: 84/126 = 2/3 after dividing both by 42.
Euclid's algorithm
Divide the larger number by the smaller and keep the remainder. Then divide the smaller number by that remainder, and so on, until the remainder is 0. The last remainder that wasn't 0 is the GCD:
- 126 ÷ 84 = 1 remainder 42
- 84 ÷ 42 = 2 remainder 0 → GCD = 42
This works quickly even for very large numbers.
GCD and LCM
For two numbers, GCD × LCM = the product of the numbers, so the LCM of 84 and 126 is 84 × 126 ÷ 42 = 252. For three or more numbers, use the GCD of multiple numbers.
The prime factor method
Write both numbers as products of primes and keep what they share. 84 = 2² × 3 × 7 and 126 = 2 × 3² × 7. The common part is 2 × 3 × 7 = 42, the GCD. Euclid's algorithm gets there with less work, and is what the calculator shows in its steps. For the factorisations, see factors of a number.
Coprime numbers
35 = 5 × 7 and 18 = 2 × 3², so they have no prime factor in common and their GCD is 1. Their LCM is then simply the product, 630. Consecutive numbers such as 14 and 15 are always coprime.
Using the GCD
To simplify a ratio or fraction, to cut a board of 84 cm and one of 126 cm into the longest equal pieces (42 cm), or to find the biggest square tile that fits a room without cutting. Three or more numbers? The GCD of multiple numbers calculator chains the steps for you.
Frequently asked questions
Is GCD the same as HCF or GCF?
Yes. Greatest common divisor (GCD), highest common factor (HCF) and greatest common factor (GCF) are three names for the same number.
What does it mean when the GCD is 1?
The numbers are coprime: they share no factor other than 1. 35 and 18 are an example, and the calculator then says "Coprime? Yes".
How does the GCD simplify a fraction?
Divide the numerator and denominator by their GCD. For 84/126 the GCD is 42, so the fraction is 2/3 in lowest terms.
Which method is faster, Euclid or prime factors?
Euclid's algorithm. It needs only repeated division with remainders, while prime factorisation of large numbers is slow. That is why the calculator uses Euclid.