🔢 GCD & LCM Calculator

GCD and LCM Explained

The Greatest Common Divisor (GCD) — also called the Greatest Common Factor (GCF) or Highest Common Factor (HCF) — is the largest positive integer that divides two or more numbers without leaving a remainder. The Least Common Multiple (LCM) is the smallest positive integer that is a multiple of two or more numbers. These two concepts are closely related and have wide applications across mathematics, engineering, music, and everyday scheduling problems.

How to Calculate GCD: The Euclidean Algorithm

The Euclidean Algorithm, developed over 2,300 years ago by the ancient Greek mathematician Euclid, is one of the oldest known algorithms still in use today. It works by repeatedly applying division with remainder:

• Step 1: Divide the larger number by the smaller, noting the remainder.
• Step 2: Replace the larger number with the smaller number, and the smaller with the remainder.
• Step 3: Repeat until the remainder is 0. The last non-zero remainder is the GCD.
• Example: GCD(48, 18) → 48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0. GCD = 6

The prime factorization method is an alternative: list all prime factors of each number, then multiply the shared factors. GCD(48, 18): 48 = 2⁴ × 3; 18 = 2 × 3²; Shared: 2¹ × 3¹ = 6. Both methods give the same answer.

How to Calculate LCM

The most efficient method uses the relationship between GCD and LCM:

• Formula: LCM(a, b) = |a × b| / GCD(a, b)
• Example: LCM(48, 18) = (48 × 18) / 6 = 864 / 6 = 144
• Verification: 144 ÷ 48 = 3 ✓; 144 ÷ 18 = 8 ✓; both divide evenly.

Alternative using prime factorization: take the highest power of each prime factor that appears in either number. 48 = 2⁴ × 3; 18 = 2 × 3²; LCM = 2⁴ × 3² = 16 × 9 = 144. ✓

Practical Applications of GCD

• Simplifying fractions: To reduce 24/36 to lowest terms, find GCD(24, 36) = 12. Divide both: 24/12 = 2, 36/12 = 3 → simplified form is 2/3.
• Equal division problems: You have 48 apples and 18 oranges. What's the maximum number of identical gift baskets you can make (using all fruit)? Answer: GCD(48, 18) = 6 baskets, each with 8 apples and 3 oranges.
• Unit conversion: Finding the largest unit that divides two measurements evenly. Two boards measuring 48 cm and 18 cm can be cut into equal pieces of maximum length 6 cm with no waste.
• Cryptography: GCD is fundamental to RSA encryption, where checking GCD(e, φ(n)) = 1 is a key step in generating encryption keys.

Practical Applications of LCM

• Adding fractions with unlike denominators: To add 1/48 + 1/18, find LCM(48, 18) = 144 as the common denominator: 3/144 + 8/144 = 11/144.
• Scheduling and timing problems: Bus A comes every 48 minutes; Bus B comes every 18 minutes. When do they next arrive at the same time? In LCM(48, 18) = 144 minutes (2 hours 24 minutes).
• Gear and mechanical engineering: When two gears with different numbers of teeth mesh, the LCM tells you how many rotations it takes for the same teeth to realign.
• Music: Notes with different frequencies find their "meeting point" at the LCM of their wavelengths, which relates to why some note combinations sound harmonious.
• Project management: Events occurring at different intervals (weekly, monthly, quarterly) align on schedules that are multiples of their LCMs.

The GCD-LCM Relationship

There's a beautiful mathematical relationship: for any two positive integers a and b, GCD(a, b) × LCM(a, b) = a × b. This identity provides a quick way to find either value when you know the other: if you know GCD(a,b) = 6 and a × b = 864, then LCM = 864 / 6 = 144. This relationship also shows why prime numbers have a GCD of 1 with any number that isn't their multiple — they share no common factors.

Frequently Asked Questions

What is the GCD of 0 and any number? By convention, GCD(0, n) = n for any positive integer n, because every positive integer divides 0 (0 = n × 0). This makes the Euclidean algorithm consistent: it terminates when the remainder reaches 0.

Can GCD and LCM be extended to more than two numbers? Yes. For three or more numbers, apply the operation iteratively: GCD(a, b, c) = GCD(GCD(a, b), c). Similarly for LCM. This extends naturally to any number of integers.

What is a coprime (or relatively prime) pair? Two numbers are coprime if their GCD equals 1 — they share no common prime factors. Examples: (4, 9), (8, 15), (14, 25). For coprime pairs, LCM(a, b) = a × b. Many important results in number theory depend on coprimality.