Greatest Common Divisor (GCD) Calculator

Calculate the GCD using the Euclidean algorithm with extended GCD for Bezout's identity. Full step-by-step solutions.

Enter Numbers

Result

Greatest Common Divisor
--

Step-by-Step Solution

GCD(a, b) using Euclidean: a = q*b + r, repeat with (b, r)

Understanding the Greatest Common Divisor

The Greatest Common Divisor (GCD), also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF), is the largest positive integer that divides each of the given integers without a remainder. It is one of the most fundamental concepts in number theory.

Methods for Computing GCD

Euclidean Algorithm

The most efficient classical algorithm. Repeatedly divide and take remainders until the remainder is zero.

GCD(a,b) = GCD(b, a mod b)

Extended Euclidean

Finds integers x and y satisfying Bezout's identity along with the GCD.

GCD(a,b) = a*x + b*y

Prime Factorization

Factor both numbers into primes and multiply the common prime factors.

GCD = product of common primes

Binary GCD (Stein's)

An optimized algorithm that uses bitwise operations instead of division.

Uses shifts and subtractions only

The Euclidean Algorithm

The Euclidean algorithm is one of the oldest known algorithms, dating back to around 300 BC. It works on the principle that GCD(a, b) = GCD(b, a mod b). By repeatedly applying this rule, we reduce the problem until we reach GCD(d, 0) = d.

  1. Start with two positive integers a and b, where a >= b.
  2. Divide a by b to get quotient q and remainder r: a = q * b + r.
  3. If r = 0, then GCD = b. We are done.
  4. Otherwise, set a = b and b = r, then go to step 2.

Extended Euclidean Algorithm

The extended version not only computes the GCD but also finds integers x and y such that a*x + b*y = GCD(a, b). This is known as Bezout's identity. The extended GCD is crucial in cryptography (computing modular multiplicative inverses for RSA), solving Diophantine equations, and Chinese Remainder Theorem applications.

Properties of GCD

  • GCD(a, 0) = |a| for any integer a
  • GCD(a, b) = GCD(b, a) (commutative)
  • GCD(a, b) = GCD(|a|, |b|) (depends only on absolute values)
  • If GCD(a, b) = 1, then a and b are coprime (relatively prime)
  • GCD(a, b) * LCM(a, b) = |a * b|
  • GCD is associative: GCD(a, b, c) = GCD(GCD(a, b), c)

Applications

  • Simplifying fractions to lowest terms
  • RSA cryptography (computing modular inverses)
  • Solving linear Diophantine equations
  • Computing least common multiples
  • Music theory (finding rhythmic patterns)
  • Computer science (hash table sizing, memory alignment)