LCM & GCF Calculator
Find the Least Common Multiple and Greatest Common Factor with prime factorization and Euclidean algorithm steps.
Enter Numbers (2–5)
Prime Factorizations
Results
GCF (Greatest Common Factor)
6
2 × 3
LCM (Least Common Multiple)
36
2^2 × 3^2
Prime Factor Analysis
| Prime | 12 | 18 | GCF (min) | LCM (max) |
|---|---|---|---|---|
| 2 | ^2 | ^1 | ^1 | ^2 |
| 3 | ^1 | ^2 | ^1 | ^2 |
Euclidean Algorithm Steps (for 2 numbers)
GCF = 6. Then LCM = 12 × 18 ÷ 6 = 36
LCM & GCF Calculator
Calculate the Least Common Multiple (LCM) and Greatest Common Factor (GCF) of 2–5 numbers using the Euclidean algorithm and prime factorization.
Guide
How it works
Euclid's Algorithm: 2,300 Years Old and Still Best
The Euclidean algorithm, described in Euclid's Elements (circa 300 BC), is one of the oldest numerical algorithms still in everyday use. It computes GCF using the observation that gcd(a, b) = gcd(b, a mod b). Starting from two numbers, repeatedly replace the larger with the remainder of dividing the two — when the remainder is 0, the other number is the GCF. For gcd(48, 18): 48 = 2×18 + 12; 18 = 1×12 + 6; 12 = 2×6 + 0. Answer: 6. This algorithm is O(log(min(a,b))) — extremely efficient even for numbers with hundreds of digits.
GCF in Real Life: Tiling and Distribution
The GCF answers: "What is the largest unit that evenly divides all given quantities?" Tiling a room: A room 12 feet × 18 feet can be tiled with the largest square tile that fits perfectly along both walls — the tile side length is GCF(12, 18) = 6 feet (or 2, 3, 6). Equal distribution: 48 apples and 60 oranges distributed into identical bags without remainder: max bags = GCF(48, 60) = 12, each with 4 apples and 5 oranges.
LCM: Scheduling and Synchronization
The LCM answers: "When will two or more periodic events next coincide?" Bus scheduling: Bus A leaves every 12 minutes, Bus B every 18 minutes. They leave together at time 0 — the next simultaneous departure is at LCM(12, 18) = 36 minutes. Gear rotation: A gear with 12 teeth meshing with one of 18 teeth returns to the same tooth alignment after LCM(12,18) / 12 = 3 full rotations of the first gear. Musical polyrhythm: A 3-beat and 4-beat pattern align every LCM(3,4) = 12 beats, creating the rhythmic cycle heard in West African and Afro-Cuban music.
Adding Fractions: Why LCM Matters
To add 1/12 + 1/18, find the Least Common Denominator = LCM(12, 18) = 36. Then 1/12 = 3/36, 1/18 = 2/36, sum = 5/36. Using LCM as the LCD gives the simplest common denominator without needing to simplify at the end. This is why LCM is taught alongside fraction arithmetic — it makes addition and subtraction of fractions systematic.
Coprime Numbers and Bézout's Identity
Two numbers are coprime (or relatively prime) when their GCF = 1. Examples: (8, 9), (14, 15), any two consecutive integers. For coprime numbers, LCM(a, b) = a × b. Bézout's identity states that for any integers a and b, there exist integers x and y such that ax + by = gcd(a, b). This theorem underlies the Extended Euclidean Algorithm, crucial for computing modular inverses in RSA encryption.
Modular Arithmetic Applications
GCF and LCM are foundational to modular arithmetic, which powers modern cryptography. RSA encryption relies on the fact that factoring large numbers (finding their prime factors) is computationally infeasible — while multiplying primes together is easy. The Euler totient function φ(n), used to select RSA keys, depends directly on the prime factorization of n. Every time you visit an HTTPS website, your browser and server are performing computations rooted in GCF and prime factorization.
What is the difference between GCF and LCM?expand_more
GCF (Greatest Common Factor, also GCD) is the largest number that divides all given numbers without remainder. LCM (Least Common Multiple) is the smallest positive number divisible by all given numbers. GCF divides down; LCM multiplies up. For any two numbers: LCM × GCF = a × b.
Can LCM or GCF be calculated for more than 2 numbers?expand_more
Yes. Apply the operation pairwise: GCF(a, b, c) = GCF(GCF(a, b), c). LCM(a, b, c) = LCM(LCM(a, b), c). This works because both GCF and LCM are associative. The prime factorization method also extends naturally: take minimum (GCF) or maximum (LCM) exponents of each prime across all numbers.
Why is GCF(a, 0) = a?expand_more
Every positive integer divides 0 (since 0 = n × 0 for any n). So the greatest common divisor of any number a and 0 is a itself — because a divides both a and 0, and no number larger than a can divide a. This base case makes the Euclidean algorithm terminate correctly.
How do I simplify a fraction using GCF?expand_more
Divide both numerator and denominator by their GCF. For 24/36: GCF(24, 36) = 12. So 24/36 = (24÷12)/(36÷12) = 2/3. This gives the fraction in lowest terms. If GCF = 1, the fraction is already fully simplified (the numerator and denominator are coprime).
What does it mean for two numbers to be coprime?expand_more
Two numbers are coprime (relatively prime) when their GCF equals 1. They share no common prime factors. Examples: 8 and 9 are coprime (8 = 2³, 9 = 3²). Consecutive integers are always coprime. In cryptography, we need large coprime numbers — RSA keys require two large primes p and q to be coprime to φ(n) = (p−1)(q−1).