LCM & GCD Calculator

Find the Least Common Multiple and Greatest Common Divisor of two or more numbers. Essential for fraction arithmetic and number theory.

Number 1

Number 2

About LCM & GCD Calculator

Understanding GCD and LCM

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 a remainder. The Least Common Multiple (LCM) is the smallest positive integer that is a multiple of each of the given numbers.

Key Relationship:

For any two positive integers a and b: LCM(a, b) × GCD(a, b) = |a × b|. This fundamental identity connects the two concepts and provides an efficient way to compute LCM from GCD.

The Euclidean Algorithm

The Euclidean algorithm is one of the oldest known algorithms, dating back to around 300 BC. It efficiently computes the GCD by repeatedly applying the division algorithm: divide the larger number by the smaller, then replace the larger with the remainder, and repeat until the remainder is zero.

Example: GCD(48, 18)

48 ÷ 18 = 2 remainder 12
18 ÷ 12 = 1 remainder 6
12 ÷ 6 = 2 remainder 0
GCD = 6 (last non-zero remainder)

Prime Factorization Method

Prime factorization decomposes a number into its prime factors. Using prime factorizations, the GCD is the product of common prime factors with the lowest exponents, while the LCM is the product of all prime factors with the highest exponents.

GCD via Prime Factors

12 = 2² × 3
18 = 2 × 3²
GCD = 2¹ × 3¹ = 6

LCM via Prime Factors

12 = 2² × 3
18 = 2 × 3²
LCM = 2² × 3² = 36

Practical Applications

GCD Applications

• Simplifying fractions
• Tiling and packing problems
• Cryptography (RSA algorithm)
• Music theory (rhythm patterns)

LCM Applications

• Adding fractions (common denominator)
• Scheduling recurring events
• Gear and pulley synchronization
• Signal processing

Frequently Asked Questions

What is the difference between GCD and LCM?

The GCD (Greatest Common Divisor) is the largest positive integer that divides two or more numbers without a remainder. The LCM (Least Common Multiple) is the smallest positive integer that is divisible by all the given numbers. For example, for 12 and 18, the GCD is 6 and the LCM is 36.

How does the Euclidean algorithm work?

The Euclidean algorithm finds the GCD by repeatedly dividing the larger number by the smaller and taking the remainder. For example, GCD(48, 18): 48 ÷ 18 = 2 remainder 12, then 18 ÷ 12 = 1 remainder 6, then 12 ÷ 6 = 2 remainder 0. Since the remainder is 0, the GCD is 6.

How is LCM calculated from GCD?

The LCM of two numbers a and b can be calculated using the formula: LCM(a, b) = |a × b| / GCD(a, b). This is more efficient than listing all multiples. For multiple numbers, compute LCM iteratively: LCM(a, b, c) = LCM(LCM(a, b), c).

What is prime factorization and how does it relate to GCD and LCM?

Prime factorization breaks a number into its prime factors (e.g., 12 = 2² × 3). The GCD is found by taking the lowest power of each common prime factor, while the LCM is found by taking the highest power of each prime factor across all numbers.

When would I use GCD and LCM in real life?

GCD is used for simplifying fractions (e.g., 12/18 simplifies to 2/3 by dividing by GCD 6), tiling problems, and distributing items equally. LCM is used for finding common denominators when adding fractions, scheduling recurring events, and synchronizing cycles.

Can GCD and LCM be calculated for more than two numbers?

Yes. For multiple numbers, compute GCD or LCM pairwise and iteratively. For example, GCD(a, b, c) = GCD(GCD(a, b), c) and LCM(a, b, c) = LCM(LCM(a, b), c). This calculator supports up to 10 numbers.

Additional Resources

Greatest Common Divisor - Wikipedia Least Common Multiple - Wikipedia LCM and GCD - Khan Academy

Share This Calculator

Include calculator values in URL

Embed on Your Website

Add this calculator to your website