GCD Calculator

The Greatest Common Divisor (GCD) — also called the Greatest Common Factor (GCF) or Highest Common Factor (HCF) — is the largest positive integer that divides all given numbers without a remainder. For example, GCD(48, 36) = 12 because 12 is the largest number that divides both 48 and 36 evenly. When the GCD of two numbers is 1, the numbers are called coprime or relatively prime — they share no common factors other than 1. Our GCD calculator computes the GCD of up to 10 integers using the Euclidean algorithm and shows every step of the calculation.

1. 1. Enter Your Integers: Type 2–10 positive integers separated by commas or spaces in the input field. Our GCD calculator accepts integers up to 1,000,000,000. Press Enter or click Calculate GCD to compute.
2. 2. Euclidean Algorithm Applied: The GCD calculator applies the Euclidean algorithm to each pair of numbers, recording every division step. For more than two numbers, it computes iteratively: GCD(a, b, c) = GCD(GCD(a, b), c). All processing happens locally in your browser — your data never leaves your device.
3. 3. Full Results Displayed: The GCD calculator shows the GCD value, prime factorizations of all inputs, all divisors of the GCD, and a complete step-by-step Euclidean algorithm table for each pair of numbers.

• The Algorithm: To find GCD(a, b) where a ≥ b: divide a by b to get quotient q and remainder r (a = b × q + r). Replace a with b and b with r. Repeat until r = 0. The last non-zero remainder is the GCD. This is one of the oldest algorithms in mathematics, described by Euclid around 300 BCE.
• Example — GCD(48, 36):
  Step 1: 48 = 36 × 1 + 12 (remainder 12)
  Step 2: 36 = 12 × 3 + 0 (remainder 0)
  → GCD = 12 (the last non-zero remainder)
• Why It Works: The key insight is that GCD(a, b) = GCD(b, a mod b). Any common divisor of a and b also divides their difference and remainder, so the GCD is preserved at each step. The algorithm terminates because the remainder strictly decreases at each step.
• GCD and Prime Factorization: The GCD can also be found by taking the prime factorization of each number and multiplying the common prime factors with their minimum exponents. For example, 48 = 2⁴ × 3 and 36 = 2² × 3², so GCD = 2² × 3 = 12. Our GCD calculator shows both methods.

• GCD × LCM = a × b: For any two positive integers a and b, GCD(a, b) × LCM(a, b) = a × b. This relationship lets you compute the LCM once you know the GCD.
• Coprime numbers:If GCD(a, b) = 1, then a and b are coprime. Consecutive integers are always coprime. Prime numbers are coprime with any number they don't divide.
• GCD(a, 0) = a: The GCD of any number and 0 is the number itself. This is the base case of the Euclidean algorithm.
• Bézout's Identity: For any integers a and b, there exist integers x and y such that ax + by = GCD(a, b). This is the foundation of the Extended Euclidean Algorithm used in cryptography.