LCM & GCD Calculator

Two Machines, Two Cycles, One Question — When Do They Sync?

Machine A runs a maintenance cycle every 6 hours. Machine B runs one every 8 hours. Both are serviced right now. When is the next time they will both need servicing at the same moment? The answer is LCM(6, 8) = 24 hours. This is what the Least Common Multiple actually solves in practice — not an abstract school exercise, but a concrete scheduling question. The same logic applies to traffic light synchronisation, medication dosing intervals, gear ratio design, and any system where two repeating processes need to be coordinated.

This free LCM and GCD calculator handles up to six numbers simultaneously, shows the prime factorization of each input, and walks through exactly how each result is derived. The verification check for two-number inputs confirms that GCD × LCM = a × b — a useful sanity check you can use to catch arithmetic errors on paper.

GCD Tells You How to Cut Things Without Waste

You need to tile a floor that is 360 cm × 480 cm using identical square tiles, with no cutting. What is the largest tile size that works? GCD(360, 480) = 120 cm — so the largest square tile you can use without cutting is 120 cm × 120 cm. The same principle applies to splitting a group of people into equal teams (GCD of the group sizes gives the largest possible team), distributing items evenly across bags, or finding the coarsest measurement unit that fits both dimensions of a structure.

In fractions, GCD is what you divide both numerator and denominator by to simplify. GCD(18, 24) = 6, so 18/24 reduces to 3/4. If you are doing that simplification as part of a larger fraction problem, the Fraction Calculator applies GCD automatically so you get simplified results without computing it separately.

How Prime Factorization Connects LCM and GCD

The step-by-step breakdown in this tool uses prime factorization to make the derivation visible. Take 12 and 18: 12 = 2² × 3, and 18 = 2 × 3². For the GCD, you take the lowest power of each prime that appears in both — min(2², 2¹) = 2¹ and min(3¹, 3²) = 3¹, giving GCD = 2 × 3 = 6. For the LCM, you take the highest power of every prime that appears anywhere — max(2², 2¹) = 2² and max(3¹, 3²) = 3², giving LCM = 4 × 9 = 36.

This prime factorization approach makes the relationship between GCD and LCM completely transparent. The verification identity — GCD × LCM = a × b — falls directly out of the factorization: every prime power appears either in the GCD or the LCM (or split between them), so multiplying them together always reconstructs the product a × b. To explore individual numbers' primality and full factorization, use the Prime Number Checker alongside this tool.

The Euclidean Algorithm — 2,300 Years Old and Still the Fastest Method

Euclid proved around 300 BCE that GCD(a, b) = GCD(b, a mod b) — meaning the GCD of two numbers equals the GCD of the smaller number and the remainder when the larger is divided by the smaller. Repeat until the remainder is zero; the last non-zero value is the GCD. For GCD(48, 18): GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6. Three steps.

What makes this remarkable is the speed — the algorithm takes at most O(log min(a,b)) steps, so even for numbers with hundreds of digits it terminates almost instantly. This is why RSA encryption still relies on it: generating public/private key pairs requires computing GCD between enormous integers, and the Euclidean algorithm handles that efficiently. For the problems this calculator addresses — school maths, engineering scheduling, fraction simplification — it runs in microseconds in your browser with no server involved.

✓Verified by ToollyX Team · Last updated June 2026