GCF & LCM Calculator

GCF and LCM calculator for up to 10 numbers with steps

This GCF and LCM calculator finds the Greatest Common Factor (GCF/GCD/HCF) and Least Common Multiple (LCM) for up to 10 positive integers at once. Enter your numbers, and the results appear instantly along with the step-by-step process — prime factorization for LCM, Euclidean algorithm steps for GCF. Add more number fields with the '+ Add number' button.

Everything runs in your browser. Nothing is sent to a server. There is no sign-up, no upload, and no limit on the size of numbers you can enter (though very large numbers may exceed JavaScript's safe integer range — for numbers over 2^53, use a bignum library).

The Euclidean algorithm — how GCF is calculated

The Euclidean algorithm is the standard method for finding GCF(a,b): repeatedly replace the larger number with the remainder of dividing the larger by the smaller, until the remainder is zero. The last non-zero number is the GCF. This runs in O(log min(a,b)) time — extremely fast even for very large numbers.

Example: GCF(252, 105). Step 1: 252 ÷ 105 = 2 remainder 42. Step 2: 105 ÷ 42 = 2 remainder 21. Step 3: 42 ÷ 21 = 2 remainder 0. GCF = 21. The calculator shows these steps so students can verify their manual working or learn the algorithm.

Prime factorization — how LCM is calculated

LCM is most transparently found via prime factorization: factor each number into primes, take the highest power of each prime that appears in any factorization, multiply. LCM(36, 48, 60): 36 = 2² × 3², 48 = 2⁴ × 3, 60 = 2² × 3 × 5. Highest powers: 2⁴, 3², 5¹. LCM = 16 × 9 × 5 = 720.

For two numbers, the shortcut is LCM(a,b) = (a × b) ÷ GCF(a,b). This is what many calculators use internally because finding GCF is fast via Euclid. For three or more numbers, the calculator chains: LCM(a,b,c) = LCM(LCM(a,b), c).

Real uses: fractions, scheduling, and coding

The most common classroom use of GCF is simplifying fractions: divide numerator and denominator by their GCF to reach lowest terms. LCM's main use is finding common denominators for adding and subtracting fractions.

In real-world scheduling, LCM answers: 'If event A repeats every 12 days and event B repeats every 8 days, when do they next coincide?' LCM(12,8) = 24 days. In programming, GCF and LCM appear in rational number arithmetic, gear ratio calculations, and tiling problems. The Euclidean algorithm for GCF is one of the oldest algorithms still in active use in modern software.

Comparing to Wolfram Alpha, Mathway, and symbolab.com

Wolfram Alpha computes GCF and LCM with full factorization details and handles extremely large numbers and symbolic inputs. It's the most powerful tool for complex cases. Mathway and Symbolab offer similar step-by-step solutions but require free accounts or a paid subscription to see the steps in full — Mathway's step view costs $9.99/month.

This tool shows steps without requiring any account. It handles up to 10 numbers simultaneously (most tools do 2–3). It loads with no advertising network overhead on the tool page. For students checking homework or developers needing a quick reference, it's faster than navigating Wolfram Alpha's general search interface or paying for a Mathway subscription.

The GCF × LCM identity: why it holds and how to use it

For any two positive integers a and b, the identity GCF(a,b) × LCM(a,b) = a × b always holds. To see why, consider the prime factorization of each number. For every prime p, the GCF takes the minimum exponent across a and b, while the LCM takes the maximum exponent. Since min(x,y) + max(x,y) = x + y for any two exponents, multiplying GCF and LCM reconstructs exactly a × b in prime form. Example: GCF(12,18) = 6 and LCM(12,18) = 36; check: 6 × 36 = 216 = 12 × 18. ✓

This identity is practically useful when you already know one value and need the other. Suppose you know GCF(a,b) = d and need the LCM — simply compute LCM = (a × b) ÷ d. This avoids factorizing from scratch. It also reveals a special case: if two numbers share no common factor greater than 1 (they are coprime, also called relatively prime), then GCF = 1, so LCM = a × b. For example, GCF(8,9) = 1, so LCM(8,9) = 72. Consecutive integers are always coprime, which is why LCM(n, n+1) = n(n+1) for any n.

The identity does not extend directly to three or more numbers. GCF(a,b,c) × LCM(a,b,c) ≠ a × b × c in general. For example, GCF(6,10,15) = 1 and LCM(6,10,15) = 30, but 6 × 10 × 15 = 900 ≠ 30. For three or more numbers, the correct approach is chaining: compute GCF or LCM of the first pair, then apply the operation again with the next number.

Extending GCF and LCM to three or more numbers

The Euclidean algorithm is associative in the sense that GCF(a,b,c) = GCF(GCF(a,b), c). This makes it straightforward to extend to any count of numbers: compute the GCF of the first two, then compute the GCF of that result with the third number, and so on. The final result is independent of the order in which the numbers are processed — you can start with any pair. For LCM, the same chaining applies: LCM(a,b,c) = LCM(LCM(a,b), c). Example: LCM(4, 6, 9) = LCM(LCM(4,6), 9) = LCM(12, 9) = 36.

Finding the GCF of n numbers via chaining requires n−1 applications of the Euclidean algorithm. Because each step reduces the problem to a smaller pair, the total time complexity remains O(n · log M) where M is the maximum input value — still very fast. In practical terms, this is how calculators and programming language standard libraries implement multi-argument GCF: Python's math.gcd accepts multiple arguments since Python 3.9, internally chaining the two-argument version. JavaScript has no built-in GCF, but the pattern is the same.

For the prime factorization approach across multiple numbers, collect all prime factors from every number, then take the lowest power of each prime that appears in every number for GCF, or the highest power of each prime that appears in any number for LCM. Example: GCF(12, 18, 24) where 12 = 2² × 3, 18 = 2 × 3², 24 = 2³ × 3. Common primes: 2 (min power is 2¹ = 1) and 3 (min power is 3¹ = 1). GCF = 2 × 3 = 6. LCM: max powers are 2³ and 3², so LCM = 8 × 9 = 72.

Historical context: Euclid's algorithm and its legacy

The algorithm for finding the greatest common divisor was recorded by the Greek mathematician Euclid around 300 BCE in his foundational work Elements, specifically in Book VII, Propositions 1 and 2. Euclid described it geometrically — as measuring two line segments by repeatedly subtracting the shorter from the longer — but the computational interpretation (using integer division with remainder) is equivalent. This makes it one of the oldest numerical algorithms in recorded history, predating the concept of zero in Western mathematics by centuries.

Despite its age, the Euclidean algorithm remains highly relevant. It achieves O(log min(a,b)) steps, which is optimal for comparison-based GCF algorithms on integers. Gabriel Lamé proved in 1844 that the number of steps never exceeds five times the number of decimal digits in the smaller number — the first result in computational complexity theory. The algorithm underpins modern cryptography: the Extended Euclidean Algorithm, a variant that also computes coefficients s and t such that GCF(a,b) = s·a + t·b (Bézout's identity), is essential in RSA encryption for computing modular inverses.

The algorithm also connects to the Fibonacci sequence in an unexpected way: consecutive Fibonacci numbers are the worst-case inputs for the Euclidean algorithm, requiring the maximum number of steps relative to the size of the numbers. GCF(F(n+1), F(n)) always equals 1, but the algorithm takes exactly n steps to prove it. This is why Fibonacci numbers appear in algorithm analysis for GCF and is the basis of Lamé's theorem.

Tiling, gears, and scheduling: applied GCF and LCM problems

The tiling problem is a classic GCF application: given a rectangular floor of dimensions a × b (in whole-number units), what is the largest square tile that fits the floor perfectly with no cutting? The answer is GCF(a,b). For a 24 × 36 floor: GCF(24,36) = 12, so 12 × 12 tiles work exactly, with 2 columns and 3 rows of tiles (24 ÷ 12 = 2, 36 ÷ 12 = 3). Replacing GCF with any smaller common factor would also tile the floor but would use more tiles than necessary.

Scheduling and cycle alignment problems are solved with LCM. If a traffic light at intersection A cycles every 45 seconds and one at intersection B cycles every 60 seconds, and both turn green simultaneously at time zero, the next time they are both green at the same moment is LCM(45,60) = 180 seconds (3 minutes). Gear ratio problems follow the same logic: if gear A has 12 teeth and gear B has 18 teeth, after LCM(12,18) ÷ 12 = 3 full rotations of A and LCM(12,18) ÷ 18 = 2 full rotations of B, both gears return simultaneously to their starting orientation. Engineers use this to identify when wear patterns repeat on meshing gears.

In music theory, LCM explains polyrhythm alignment. A 3-against-4 polyrhythm (triplets against quarter notes) fully cycles every LCM(3,4) = 12 subdivisions. The GCF tells you the largest common rhythmic unit. In computer science, memory alignment requires finding addresses that are multiples of a word size; determining the smallest such address for two different alignment requirements uses LCM. Cryptography uses GCF directly in the RSA key generation step, where the key pair is valid only when GCF(e, φ(n)) = 1, i.e., the public exponent e must be coprime to the totient of n.