GCD & LCM Calculator

What are GCD and LCM?

Greatest Common Divisor (GCD)

The Greatest Common Divisor (also called Greatest Common Factor or Highest Common Factor) is the largest positive integer that divides each of the given numbers without leaving a remainder.

For example, GCD(12, 18) = 6 because:

• Divisors of 12: 1, 2, 3, 4, 6, 12
• Divisors of 18: 1, 2, 3, 6, 9, 18
• Common divisors: 1, 2, 3, 6
• Greatest common divisor: 6

Least Common Multiple (LCM)

The Least Common Multiple is the smallest positive integer that is divisible by each of the given numbers.

For example, LCM(4, 6) = 12 because:

• Multiples of 4: 4, 8, 12, 16, 20...
• Multiples of 6: 6, 12, 18, 24...
• Common multiples: 12, 24, 36...
• Least common multiple: 12

GCD and LCM in Geocaching

These mathematical concepts appear in various puzzle cache types:

• Fraction reduction: Simplify coordinates using GCD
• Cycle puzzles: Find when events align using LCM
• Number theory puzzles: Coprime checks and factor analysis
• Pattern recognition: Finding common factors in sequences

How We Calculate GCD

We use the Euclidean Algorithm, one of the oldest known algorithms:

1. Divide the larger number by the smaller
2. Replace the larger with the smaller, and the smaller with the remainder
3. Repeat until the remainder is 0
4. The GCD is the last non-zero remainder

Example: GCD(48, 18)

• 48 ÷ 18 = 2 remainder 12
• 18 ÷ 12 = 1 remainder 6
• 12 ÷ 6 = 2 remainder 0
• GCD = 6

The GCD-LCM Relationship

For any two numbers a and b:

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

This means once you know the GCD, you can easily calculate the LCM:

LCM(a, b) = (a × b) / GCD(a, b)

Prime Factorization Method

You can also find GCD and LCM using prime factorization:

• GCD: Product of common prime factors with minimum powers
• LCM: Product of all prime factors with maximum powers

Example: For 12 = 2² × 3 and 18 = 2 × 3²

• GCD = 2¹ × 3¹ = 6 (minimum powers)
• LCM = 2² × 3² = 36 (maximum powers)

Coprime Numbers

Two numbers are coprime (or relatively prime) if their GCD is 1. This means they share no common factors other than 1.

Examples of coprime pairs:

• 8 and 15 (GCD = 1)
• 14 and 25 (GCD = 1)
• Any two consecutive integers
• Any two prime numbers

Multiple Numbers

Our calculator handles more than two numbers. For GCD and LCM of multiple numbers:

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

Practical Applications

Simplifying Fractions

To reduce a fraction to lowest terms, divide numerator and denominator by their GCD:
18/24 = (18÷6)/(24÷6) = 3/4

Synchronization Problems

If events occur every A and B units of time, they coincide every LCM(A, B) units.
A bell rings every 12 minutes, another every 18 minutes. They ring together every LCM(12, 18) = 36 minutes.