What is the Greatest Common Divisor?
The greatest common divisor (GCD), also called the highest common factor (HCF), of two integers is the largest positive integer that divides both numbers without leaving a remainder. For example, the GCD of 48 and 36 is 12, because 12 is the biggest number that goes evenly into both. This GCD Calculator instantly finds that value and also reports the least common multiple (LCM).
How to use this calculator
Enter your two whole numbers in the fields labelled A and B, then read the result. The tool takes the absolute value of each input, so negative numbers are handled correctly. If you enter 0 for one number, the GCD equals the other number (since every integer divides 0).
The Euclidean algorithm explained
This calculator uses the Euclidean algorithm, one of the oldest algorithms still in common use. It relies on a simple fact: \(\gcd(a, b) = \gcd(b, a \bmod b)\). You repeatedly replace the larger number with the remainder of dividing the two numbers, until the remainder reaches 0. The last nonzero divisor is the GCD. This avoids factoring the numbers and is extremely fast even for huge inputs.
Worked example
Find \(\gcd(48, 36)\):
$$48 \bmod 36 = 12 \rightarrow \gcd(36, 12)$$$$36 \bmod 12 = 0 \rightarrow \gcd(12, 0) = 12$$The LCM is then $$\frac{|48 \times 36|}{12} = \frac{1728}{12} = 144.$$
FAQ
What is the difference between GCD and HCF? None — they are two names for the same value. "Greatest common divisor" is common in the US; "highest common factor" is common in the UK.
What is the GCD of two coprime numbers? It is always 1. Numbers like 8 and 15 share no common factor other than 1, so they are called coprime or relatively prime.
Can the GCD be larger than the smaller number? No. The GCD can never exceed the smaller of the two inputs, and it equals the smaller number exactly when that number divides the larger one.
