GCD Calculator

Find the Greatest Common Divisor (GCD) of two or more numbers using the Euclidean algorithm with step-by-step solutions

✓ Euclidean algorithm ✓ Multiple numbers ✓ Prime factorization

Calculate GCD

GCD Properties

GCD(a, 0) = a
GCD(a, b) = GCD(b, a)
GCD(a, b) = GCD(a-b, b)
GCD(a, b) × LCM(a, b) = a × b
If GCD(a, b) = 1, then a and b are coprime

Common Examples

GCD(12, 8) 4
GCD(15, 25) 5
GCD(21, 14) 7
GCD(9, 12) 3
GCD(7, 11) 1

Applications

Fraction Simplification
Reducing fractions to lowest terms
Cryptography
RSA algorithm and key generation
Computer Science
Algorithm optimization
Number Theory
Mathematical proofs and theorems
Advertisement

Understanding GCD

The Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides each of the integers without a remainder.

Euclidean Algorithm

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

Alternative Names

  • Greatest Common Factor (GCF)
  • Highest Common Factor (HCF)
  • Greatest Common Measure (GCM)

Methods to Find GCD

Euclidean Algorithm

Most efficient method using repeated division. Time complexity: O(log min(a,b))

Prime Factorization

Find prime factors of each number and take the product of common factors with lowest powers.

Listing Factors

List all factors of each number and find the largest common factor. Good for small numbers.

Binary GCD

Stein's algorithm using binary operations, efficient for computer implementation.