Greatest Common Divisor Calculator
Find the greatest common divisor (GCD) of two or more positive integers. Enter your numbers and click Calculate — the result includes step-by-step Euclidean algorithm output for two-number inputs.
Notes
What Is the Greatest Common Divisor?
The greatest common divisor (GCD) of two or more integers is the largest positive integer that divides all of them without leaving a remainder. It is also called the highest common factor (HCF) or greatest common factor (GCF).
The Euclidean Algorithm
The Euclidean algorithm is the most efficient method for computing GCD. It repeatedly replaces the larger number with the remainder of dividing the two numbers until the remainder is zero. The last non-zero remainder is the GCD.
- Divide a by b to get a remainder r (r = a mod b).
- Replace a with b and b with r.
- Repeat until b = 0.
- The GCD is the final non-zero value of a.
Quick Example
GCD(48, 36): 48 = 36 × 1 + 12 → GCD(36, 12): 36 = 12 × 3 + 0 → GCD = 12.
- How GCD works — full explanation — Euclidean algorithm, prime factorization method, and applications
- GCD formula reference — Formula, variables, and worked examples
Frequently Asked Questions
What is GCD used for?
GCD is used to simplify fractions (divide numerator and denominator by their GCD), find common denominators, solve Diophantine equations, and in cryptography (RSA key generation uses extended Euclidean algorithm).
What is the GCD of two prime numbers?
The GCD of any two distinct prime numbers is always 1, because primes have no common factors other than 1. For example, GCD(7, 13) = 1.
What is the difference between GCD, HCF, and GCF?
They are all the same concept with different names. GCD = Greatest Common Divisor, HCF = Highest Common Factor, GCF = Greatest Common Factor. All refer to the largest integer that divides all given numbers exactly.
Can GCD be 1?
Yes. When GCD(a, b) = 1, the numbers are called coprime or relatively prime. They share no common factors other than 1. Example: GCD(8, 15) = 1.
How do I find GCD of more than two numbers?
Apply GCD pairwise: GCD(a, b, c) = GCD(GCD(a, b), c). For example, GCD(12, 18, 24) = GCD(GCD(12, 18), 24) = GCD(6, 24) = 6.