GCD and LCM Calculator

Calculate the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two or more numbers with step-by-step solutions.

Number of Inputs

Number A

Number B

Understanding GCD and LCM

The Greatest Common Divisor and Least Common Multiple are fundamental concepts in number theory with wide applications in mathematics, computer science, and everyday problem solving.

Greatest Common Divisor (GCD)

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

Example: GCD(12, 18) = 6 because 6 is the largest number that divides both 12 and 18.

Least Common Multiple (LCM)

The LCM of two or more integers is the smallest positive integer that is divisible by each of the numbers. It is the smallest number that appears in all of their multiplication tables.

Example: LCM(4, 6) = 12 because 12 is the smallest number divisible by both 4 and 6.

Key Relationship

For any two positive integers a and b:

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

This identity provides an efficient way to compute the LCM once the GCD is known: LCM(a, b) = (a × b) / GCD(a, b).

Methods for Finding GCD

Euclidean Algorithm

The most efficient classical method, based on the principle that GCD(a, b) = GCD(b, a mod b):

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

Prime Factorization Method

Uses the fundamental theorem of arithmetic:

1. Find the prime factorization of each number
2. GCD = product of common prime factors with the lowest powers
3. LCM = product of all prime factors with the highest powers

Listing Divisors

A straightforward approach for small numbers:

1. List all divisors of each number
2. Find the common divisors
3. The greatest common divisor is the GCD

Binary GCD (Stein's Algorithm)

An efficient algorithm using only subtraction and bit shifts:

1. If both even: GCD(a, b) = 2 × GCD(a/2, b/2)
2. If one even: GCD(a, b) = GCD(a/2, b) or GCD(a, b/2)
3. If both odd: GCD(a, b) = GCD(|a − b|/2, min(a, b))
4. Repeat until one value is 0

Real-World Applications

Simplifying fractions: Divide numerator and denominator by their GCD to reduce to lowest terms
Adding fractions: The LCM of the denominators gives the least common denominator
Scheduling: LCM determines when periodic events with different cycles will coincide (e.g., bus schedules, gear rotations)
Cryptography: GCD is central to the RSA algorithm and modular arithmetic used in encryption
Music theory: Finding common rhythmic patterns and time signatures
Tiling problems: GCD determines the largest square tile that can perfectly cover a rectangular floor
Computer science: Used in hash functions, random number generators, and algorithm design

References

The algorithms and formulas used in this calculator are based on well-established number theory principles:

Related Calculators

Fraction Simplifier Arithmetic Sequence Calculator Probability Calculator

This calculator computes GCD and LCM using the Euclidean algorithm and prime factorization. Results are for educational and informational purposes. While we strive for accuracy, please verify important calculations independently. Very large numbers may experience floating-point precision limitations.

As an Amazon Associate, we earn from qualifying purchases.

Recommended Calculator

Casio FX-991ES Plus

The professional-grade scientific calculator with 417 functions, natural display, and solar power. Perfect for students and professionals.

View on Amazon