GCD Calculator

Results:

Understanding GCD and LCM

Greatest Common Divisor (GCD)

The GCD of two or more integers is the largest positive integer that divides each of the numbers without a remainder. It's also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF).

For integers a and b:

GCD(a,b) = max{d ∈ ℤ⁺ : d|a and d|b}

Euclidean Algorithm: GCD(a,b) = GCD(b, a mod b)

Properties and Applications

Key Properties of GCD

  • GCD(a,b) = GCD(|a|,|b|)
  • GCD(a,b) = GCD(b,a)
  • GCD(a,0) = |a|
  • GCD(a,1) = 1
  • If a|b, then GCD(a,b) = |a|
  • GCD(a,b) × LCM(a,b) = |a × b|

Applications

  • Fraction simplification
  • Cryptography (RSA algorithm)
  • Computer graphics (scaling)
  • Music theory (rhythm patterns)
  • Engineering design

Advanced Topics

Bézout's Identity

For any two integers a and b, there exist integers x and y such that:

ax + by = GCD(a,b)

Found using Extended Euclidean Algorithm

Multiple Numbers GCD

For multiple numbers:

GCD(a,b,c) = GCD(GCD(a,b),c)

Property: Associative and Commutative

Least Common Multiple (LCM)

The LCM of two or more integers is the smallest positive integer that is divisible by each of the numbers.

LCM(a,b) = |a × b| ÷ GCD(a,b)

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