LCM and GCD Calculator

What GCD and LCM Are?

Greatest Common Divisor (GCD), also called Highest Common Factor (HCF): the largest number that divides all the given numbers exactly (without remainder). Example: GCD of 12 and 18. Factors of 12: 1, 2, 3, 4, 6, 12. Factors of 18: 1, 2, 3, 6, 9, 18. Common factors: 1, 2, 3, 6. Greatest: 6. So GCD(12, 18) = 6. Lowest Common Multiple (LCM): the smallest number that all the given numbers divide into exactly. Example: LCM of 12 and 18. Multiples of 12: 12, 24, 36, 48, 60... Multiples of 18: 18, 36, 54... The first common multiple appearing in both lists, 36, is the LCM.

What should I know about Finding GCD?

Method 1 — Prime factorisation: break each number into prime factors. 12 = 2² × 3. 18 = 2 × 3². GCD = product of LOWEST power of each common prime. Common primes: 2 (lowest power 2¹) and 3 (lowest power 3¹). GCD = 2 × 3 = 6. Method 2 — Euclidean algorithm (faster for large numbers): repeatedly divide and take remainders. GCD(48, 18): 48 = 2×18 + 12. GCD(18, 12): 18 = 1×12 + 6. GCD(12, 6): 12 = 2×6 + 0. Remainder is 0, so GCD = 6 (the last non-zero remainder). The Euclidean algorithm is extremely efficient even for very large numbers, since it converges in relatively few steps regardless of how big the starting values are.

What do I need to know about Finding LCM?

Method 1 — Prime factorisation: break each into primes. 12 = 2² × 3. 18 = 2 × 3². LCM = product of HIGHEST power of each prime appearing. Primes: 2 (highest 2²) and 3 (highest 3²). LCM = 2² × 3² = 4 × 9 = 36. Method 2 — Using GCD: LCM(a, b) = (a × b) / GCD(a, b). LCM(12, 18) = (12 × 18) / 6 = 216 / 6 = 36. Fast once you have GCD. For more than two numbers: LCM(a, b, c) = LCM(LCM(a, b), c). Apply pairwise. Note: the GCD × LCM = product relationship only works for TWO numbers, not three or more. For three or more numbers, calculate the LCM of the first two, then find the LCM of that result with the next number, repeating until all numbers are included.

What's the key thing to understand about Real-World Applications?

Fractions: GCD simplifies fractions to lowest terms. 12/18 = (12÷6)/(18÷6) = 2/3. LCM finds common denominators. 1/12 + 1/18: LCM = 36. = 3/36 + 2/36 = 5/36. Scheduling/timing: two buses leave at intervals of 12 and 18 minutes. When do they coincide? LCM(12,18) = 36 minutes. Three machines cycle every 4, 6, 8 seconds — synchronise every LCM(4,6,8) = 24 seconds. Tiling and packing: largest square tile fitting a 12×18 area without cutting: GCD(12,18) = 6cm tiles. Gear ratios: teeth counts and rotation speeds of meshing gears use LCM to determine how many rotations each gear completes before the same teeth mesh together again.

What should I know about the Euclidean Algorithm?

The Euclidean Algorithm is the fastest standard method for finding the GCD of two numbers without factoring either one. It repeatedly replaces the larger number with the remainder of dividing it by the smaller number, until the remainder is zero — the last non-zero remainder is the GCD. For example, to find GCD(252, 105): 252 = 2×105 + 42, then 105 = 2×42 + 21, then 42 = 2×21 + 0, so GCD(252, 105) = 21. This method works for any two positive integers, however large, and is far faster than listing factors for big numbers, which is why it's the algorithm used inside calculators, cryptographic software (like RSA key generation), and computer algebra systems whenever a GCD needs to be computed quickly.

What's the key thing to understand about the Relationship Between GCD and LCM (GCD × LCM = a × b)?

For any two positive integers a and b, their GCD and LCM are linked by the identity GCD(a,b) × LCM(a,b) = a × b. This gives a fast shortcut for finding one once you know the other: LCM(a,b) = (a × b) / GCD(a,b). For example, GCD(12, 18) = 6, so LCM(12, 18) = (12 × 18)/6 = 216/6 = 36, without needing to list multiples. This identity also explains why two coprime numbers (GCD = 1), like 8 and 15, always have an LCM equal to their simple product (120) — there's no shared factor to "cancel" when combining them, so nothing smaller than the full product can be a common multiple.

What should I know about Coprime Numbers and Fraction Simplification?

Two integers are called coprime (or relatively prime) when their greatest common divisor is 1, meaning they share no common factors other than 1 itself — for example, 8 and 15 are coprime even though neither is prime, since their only shared divisor is 1. This concept is central to simplifying fractions: a fraction a/b is in its simplest (lowest) form precisely when its numerator and denominator are coprime, since any shared factor larger than 1 could still be cancelled. This is exactly why finding the GCD of a fraction's numerator and denominator, then dividing both by it, always produces the simplest equivalent fraction in one step: dividing both by their GCD guarantees the resulting pair of numbers is coprime, since any remaining common factor would have been part of the GCD itself. Coprimality also governs when the shortcut formula LCM(a,b) = a × b for the lowest common multiple applies: it only holds when a and b are coprime, since otherwise the shared factors would be double-counted, which is why the general formula LCM(a,b) = (a × b)/GCD(a,b) is always needed for numbers that are not coprime. Coprime pairs also appear throughout number theory, including in generating Pythagorean triples and in cryptographic algorithms like RSA, which rely on selecting numbers that are coprime to a chosen modulus.

GCD and LCM Reference Table for Common Number Pairs

A quick-reference table showing GCD and LCM for frequently-encountered number pairs, useful for checking fraction simplification or scheduling problems:

Note the pair (8, 9): their GCD is 1, meaning they are coprime (share no common factors besides 1), and for any coprime pair, the LCM always equals the simple product of the two numbers (8 × 9 = 72) — a useful shortcut that skips the full LCM calculation entirely whenever you can spot that two numbers share no factors.

Worked Example: GCD and LCM of Three Numbers via Prime Factorization

Find the GCD and LCM of 36, 48, and 60 using prime factorization. Prime factorize each: 36 = 2² × 3², 48 = 2⁴ × 3¹, 60 = 2² × 3¹ × 5¹. GCD — take the lowest power of each prime that appears in ALL three numbers. The prime 2 appears as 2², 2⁴, 2² → lowest is 2². The prime 3 appears as 3², 3¹, 3¹ → lowest is 3¹. The prime 5 appears only in 60, not in 36 or 48, so it's excluded entirely. GCD = 2² × 3¹ = 4 × 3 = 12. LCM — take the highest power of each prime that appears in ANY of the three numbers. 2: highest power is 2⁴ (from 48). 3: highest power is 3² (from 36). 5: highest power is 5¹ (from 60). LCM = 2⁴ × 3² × 5¹ = 16 × 9 × 5 = 720. Quick check: 720 ÷ 36 = 20 (whole number ✓), 720 ÷ 48 = 15 (whole number ✓), 720 ÷ 60 = 12 (whole number ✓) — confirming 720 is indeed a common multiple of all three, and 12 divides into 36, 48, and 60 evenly as well (3, 4, and 5 respectively), confirming the GCD.

Using GCD to Simplify Fractions to Lowest Terms

The fastest way to simplify any fraction to lowest terms is to divide both the numerator and denominator by their GCD. Simplify 84/126. Find GCD(84, 126) via prime factorization: 84 = 2² × 3 × 7, 126 = 2 × 3² × 7. Taking the lowest power of each shared prime: GCD = 2¹ × 3¹ × 7¹ = 2 × 3 × 7 = 42. Divide both parts by the GCD: 84/42 = 2, and 126/42 = 3. So 84/126 simplifies to 2/3. Check: 2/3 = 0.6667, and 84/126 = 0.6667 — matching, confirming the simplification is correct and that 2/3 is indeed in lowest terms (since GCD(2,3) = 1, they're coprime). This GCD-based shortcut works for any fraction, no matter how large the numbers, and is exactly what a "simplify fraction" feature does internally in spreadsheet software and calculators — find the GCD first, then divide both parts by it in a single step rather than repeatedly dividing by small common factors one at a time.