GCD Calculator (Greatest Common Divisor)

Find the greatest common divisor of two or more numbers using the Euclidean algorithm, with step-by-step division. Also computes the LCM.

Enter Numbers

Enter two or more positive integers separated by commas. The calculator will find the GCD using the Euclidean algorithm and also compute the LCM.

Quick Examples

Result

Greatest Common Divisor (GCD)
--
Input Numbers --
GCD --
LCM --
Coprime? --

Euclidean Algorithm Steps

GCD(a, b) via Euclidean algorithm

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 numbers without leaving a remainder. For example, GCD(12, 8) = 4 because 4 is the largest number that divides both 12 and 8 evenly.

The GCD is a fundamental concept in number theory with applications in simplifying fractions, computing modular arithmetic, cryptography (RSA algorithm), and solving Diophantine equations.

Methods for Finding GCD

Euclidean Algorithm

Repeatedly divide and take remainders. GCD(a,b) = GCD(b, a mod b) until remainder is 0.

GCD(48,36) -> GCD(36,12) -> GCD(12,0) = 12

Prime Factorization

Factor each number into primes, then multiply the common prime factors with lowest exponents.

48=2^4*3, 36=2^2*3^2 -> GCD=2^2*3=12

GCD-LCM Relationship

For two numbers a and b, the product of GCD and LCM equals a times b.

GCD(a,b) x LCM(a,b) = a x b

Multiple Numbers

GCD of multiple numbers is computed iteratively: GCD(a,b,c) = GCD(GCD(a,b), c).

GCD(12,18,24) = GCD(GCD(12,18),24) = GCD(6,24) = 6

The Euclidean Algorithm

The Euclidean algorithm is one of the oldest algorithms still in common use, dating back to Euclid's Elements (circa 300 BC). It is efficient, elegant, and guaranteed to terminate. The algorithm works as follows:

  1. Given two numbers a and b (where a >= b > 0), divide a by b to get quotient q and remainder r.
  2. If r = 0, then GCD = b. Done.
  3. Otherwise, replace a with b and b with r, and repeat from step 1.

Computing LCM from GCD

The Least Common Multiple (LCM) of two numbers can be easily computed once you know the GCD:

LCM(a, b) = |a x b| / GCD(a, b)

For multiple numbers, compute iteratively: LCM(a, b, c) = LCM(LCM(a, b), c).

Practical Applications

  • Simplifying fractions: Divide numerator and denominator by their GCD.
  • Cryptography: The Extended Euclidean Algorithm is used in RSA key generation.
  • Music theory: GCD helps find rhythmic patterns and beat synchronizations.
  • Engineering: Finding common measurement units and gear ratios.

Properties of GCD

  • GCD(a, 0) = a for any non-negative integer a.
  • GCD(a, b) = GCD(b, a) (commutativity).
  • GCD(a, b, c) = GCD(GCD(a, b), c) (associativity).
  • GCD(a, b) = GCD(a - b, b) if a > b (subtraction-based form).
  • If GCD(a, b) = 1, then a and b are called coprime or relatively prime.