GCD Calculator
Greatest common divisor of two numbers.
Inputs
Loading calculator…
Calculating…
Was this helpful?
Formula
GCD(a, b) via Euclidean algorithm: repeatedly replace (a, b) with (b, a mod b) until b = 0
The greatest common divisor (also called HCF) is the largest positive integer that divides both numbers without a remainder. The Euclidean algorithm finds it efficiently without factoring.
Worked example
GCD(48, 18) is 6 — the largest number that divides both 48 and 18 evenly. The Euclidean steps are 48 mod 18 = 12, then 18 mod 12 = 6, then 12 mod 6 = 0, so the answer is 6.
Where this can give the wrong answer
- Both inputs must be positive integers (minimum 1) — the algorithm relies on repeated modulo operations on whole numbers.
- When one number divides the other, the GCD is the smaller number — GCD(18, 54) = 18.
- Coprime numbers have GCD 1 — e.g. GCD(8, 15) = 1, meaning they share no common factor other than 1.
FAQ
- Yes — Greatest Common Divisor and Highest Common Factor are the same thing. Indian school textbooks tend to say HCF; computer science and number theory tend to say GCD.