LCM & GCF Calculator & Solver
Calculate the Least Common Multiple (LCM) and Greatest Common Factor (GCF / HCF / GCD) of two or three numbers with full step-by-step prime factorization and Euclidean division.
Comprehensive Guide: Least Common Multiple (LCM) & Greatest Common Factor (GCF)
Master the dual pillars of number theory, the Euclidean division algorithm, prime factor lattices, and their role in fraction arithmetic and modular systems.
1. Fundamental Definitions of LCM and GCF in Number Theory
In elementary number theory, the Greatest Common Factor (GCF)—also termed the Greatest Common Divisor (GCD)—and the Least Common Multiple (LCM) represent dual aspects of integer divisibility:
- Greatest Common Factor (GCF): For two integers
aandb(not both zero),gcd(a, b)is the largest positive integer that divides bothaandbwithout remainder. It measures the maximum scale of uniform division. - Least Common Multiple (LCM): For two non-zero integers
aandb,lcm(a, b)is the smallest positive integer that is simultaneously divisible by bothaandb. It measures the earliest recurrence point of periodic cycles.
2. The Fundamental Product Theorem Connecting LCM & GCF
There is a profound, universal relationship linking the product of any two positive integers to their GCF and LCM:
This theorem provides the most computationally efficient algorithm for computing the LCM: calculate the GCF first via Euclid's algorithm, then divide their product by that GCF. This avoids generating massive lists of multiples.
3. Algorithmic Methods: Prime Lattice vs. Euclidean Algorithm
The Prime Factorization Lattice Rule
If we decompose numbers into their canonical prime powers:
a = p₁^(α₁) × p₂^(α₂) × ... × pₖ^(αₖ)
b = p₁^(β₁) × p₂^(β₂) × ... × pₖ^(βₖ)
Then GCF takes the minimum exponent for each prime, while LCM takes the maximum exponent:
gcd(a, b) = p₁^(min(α₁, β₁)) × p₂^(min(α₂, β₂)) × ...lcm(a, b) = p₁^(max(α₁, β₁)) × p₂^(max(α₂, β₂)) × ...
Euclidean Division Algorithm for GCF
To find gcd(a, b), repeatedly compute remainders: a = q × b + r. Replace (a, b) with (b, r) until r = 0. The last non-zero divisor is the GCF.
4. Step-by-Step Worked Example: Numbers 72 and 120
Step 1: Prime Factor Decomposition
72 = 2³ × 3²
120 = 2³ × 3¹ × 5¹
Step 2: Calculate GCF (Minimum Exponents)
For prime 2: min(3, 3) = 2³ = 8
For prime 3: min(2, 1) = 3¹ = 3
For prime 5: min(0, 1) = 5⁰ = 1
GCF(72, 120) = 8 × 3 × 1 = 24.
Step 3: Calculate LCM (Maximum Exponents)
For prime 2: max(3, 3) = 2³ = 8
For prime 3: max(2, 1) = 3² = 9
For prime 5: max(0, 1) = 5¹ = 5
LCM(72, 120) = 8 × 9 × 5 = 360.
Step 4: Verify via Product Theorem
72 × 120 = 8,640
GCF × LCM = 24 × 360 = 8,640 ✓ (Exact Identity Holds).
5. Real-World Applications in Engineering & Everyday Scheduling
- Synchronizing Periodic Cycles (LCM): If Bus A arrives every 12 minutes and Bus B arrives every 18 minutes, they will arrive simultaneously at
lcm(12, 18) = 36minutes past the hour. - Tiling & Packaging Optimization (GCF): If you have a floor measuring 120 cm by 168 cm and want to tile it with the largest possible square tiles without cutting, the tile edge must equal
gcd(120, 168) = 24 cm. - Common Denominators in Fraction Arithmetic: Adding fractions with unlike denominators requires finding the Least Common Denominator (LCD), which is identical to the LCM of the denominators.
6. Frequently Asked Questions (FAQ)
What is the GCF of two prime numbers?
Because distinct prime numbers share no divisors other than 1, the GCF of any two distinct primes p and q is always strictly 1 (they are mutually coprime), and their LCM is simply their product p × q.
Does the product formula a × b = GCF × LCM work for three numbers?
No! For three numbers a, b, c, a × b × c ≠ gcd(a,b,c) × lcm(a,b,c). The relationship for three or more numbers requires the inclusion-exclusion principle across pair-wise GCFs.