GCD Calculator (Greatest Common Divisor)
Finds the greatest common divisor (GCD), also called the greatest common factor (GCF) or highest common factor (HCF), of up to 15 whole numbers: the largest number that divides all of them without a remainder. Enter the numbers separated by commas or spaces and choose how to see the working: the Euclidean algorithm step by step, or the prime factorization of each number with the shared factors picked out. The least common multiple is shown too.
- Inputs are whole numbers up to 10¹²; signs are ignored.
Formula
Euclid: GCD(a, b) = GCD(b, a mod b), until the remainder is 0; GCD(a, b, c) = GCD(GCD(a, b), c)
- With prime factorizations, the GCD is the product of the primes common to all numbers, each raised to its smallest exponent.
- GCD × LCM = a × b for two positive numbers.
- Negative signs are ignored; GCD(n, 0) = n.
- Numbers up to 1,000,000,000,000 are accepted.
GCD of 48, 180 and 300
Inputs
- Numbers: 48, 180, 300
- Show the working by: euclid
180 = 3 × 48 + 36, 48 = 1 × 36 + 12, 36 = 3 × 12 + 0, so GCD(48, 180) = 12. Then 300 = 25 × 12 + 0, so the GCD of all three is 12. Check: 48 = 2⁴ × 3, 180 = 2² × 3² × 5, 300 = 2² × 3 × 5²; shared factors 2² × 3 = 12.
Sources & references
Frequently asked questions
What is the GCD?
The greatest common divisor of two or more whole numbers is the largest number that divides each of them exactly. GCD(12, 18) = 6.
Is GCD the same as GCF and HCF?
Yes. Greatest common divisor, greatest common factor and highest common factor are three names for the same thing.
How does the Euclidean algorithm work?
Replace the larger number by the remainder when it is divided by the smaller, and repeat. When the remainder reaches 0, the other number is the GCD. For 252 and 105: 252 = 2 × 105 + 42, 105 = 2 × 42 + 21, 42 = 2 × 21 + 0, so the GCD is 21.
What does it mean if the GCD is 1?
The numbers are coprime (relatively prime): they share no factor other than 1, such as 8 and 15.
Related calculators
LCM Calculator (Least Common Multiple) Finds the least common multiple (LCM) of up to 15 whole numbers: the smallest positive number that every one of them divides into exactly. Use it to find a common denominator for fractions or to work out when repeating events line up. Choose how to see the working: listing multiples, prime factorization with the highest power of each prime, or the shortcut LCM(a, b) = a × b ÷ GCD(a, b). The greatest common divisor is shown too. Prime Factorization Calculator Breaks a whole number down into the prime numbers that multiply to give it, such as 360 = 2³ × 3² × 5, for any number up to one trillion. The step-by-step division table shows how the number is divided by its smallest prime factor again and again until 1 is left. You also learn whether the number is prime, how many divisors it has, their sum, and the full list of divisors for numbers that do not have too many. Fraction Calculator Adds, subtracts, multiplies and divides two fractions, simplifies a fraction to lowest terms, and converts between fractions and decimals. Fractions can be entered as simple fractions (7/4) or as mixed numbers (1 3/4). Every answer is reduced to lowest terms and also given as a mixed number, an exact decimal with any repeating digits marked, and a decimal rounded to six places, together with the working: the common denominator for addition and subtraction or the reciprocal for division.