What is the difference between GCD and LCM?

The GCD (greatest common divisor) is the largest integer that divides all the given numbers exactly. The LCM (least common multiple) is the smallest positive integer that all the given numbers divide into exactly. For example, GCD(12, 18) = 6 because 6 is the largest number that divides both 12 and 18. LCM(12, 18) = 36 because 36 is the smallest number that both 12 and 18 divide into without a remainder.

How does the Euclidean algorithm calculate GCD?

The Euclidean algorithm finds GCD by repeated division. For GCD(a, b), divide a by b to get remainder r. Then replace a with b and b with r, and repeat until the remainder is 0. The last non-zero remainder is the GCD. For example: GCD(48, 18) → 48 = 2 × 18 + 12 → 18 = 1 × 12 + 6 → 12 = 2 × 6 + 0 → GCD = 6.

What is the relationship between GCD and LCM?

For two numbers a and b, GCD(a, b) × LCM(a, b) = a × b. This means LCM(a, b) = (a × b) / GCD(a, b). For example, GCD(4, 6) = 2 and LCM(4, 6) = 12, and indeed 2 × 12 = 4 × 6 = 24. This relationship provides the most efficient way to calculate LCM from GCD.

How do you find LCM using prime factorization?

To find LCM using prime factorization: first, write each number as a product of prime powers. Then, for each prime that appears in any number, take the highest power it appears in any single number. Multiply these highest powers together. For example, LCM(12, 18): 12 = 2² × 3 and 18 = 2 × 3². Taking highest powers: 2² and 3², so LCM = 4 × 9 = 36.

What is GCD used for in real life?

GCD has many practical uses. Simplifying fractions: to reduce 12/18 to lowest terms, divide both by GCD(12, 18) = 6 to get 2/3. Dividing objects into equal groups: if you have 12 apples and 18 oranges and want to make identical gift bags with no leftovers, GCD(12, 18) = 6 means you can make 6 bags each with 2 apples and 3 oranges. Simplifying ratios: a 12:18 ratio simplifies to 2:3.

What is LCM used for in real life?

LCM is used for synchronization and scheduling problems. If Bus A runs every 12 minutes and Bus B runs every 18 minutes, LCM(12, 18) = 36 tells you they next depart together in 36 minutes. LCM also gives the lowest common denominator for adding fractions — to add 1/12 + 1/18, use denominator 36. In engineering, LCM synchronizes repeating cycles such as gear ratios and signal frequencies.

Can GCD be larger than both numbers?

No. The GCD of two or more numbers can never be larger than the smallest of those numbers, because a divisor of a number cannot exceed the number itself. GCD is always at least 1 (since 1 divides every integer), and at most equal to the smallest number in the set (when the smallest number divides all others). For example, GCD(6, 12) = 6 because 6 is the smallest number and it divides 12 exactly.

What is the GCD of any number and 1?

GCD(n, 1) = 1 for any integer n, because 1 is the only positive integer that divides 1. Similarly, GCD(n, 0) = n for any positive integer n, because every positive integer divides 0. These are the base cases of the Euclidean algorithm — the algorithm terminates when one input reaches 0, and the GCD is the other input.

How do you find LCM and GCD for more than two numbers?

For three or more numbers, apply the two-number algorithm iteratively. For GCD(a, b, c) = GCD(GCD(a, b), c). For LCM(a, b, c) = LCM(LCM(a, b), c). For example, GCD(12, 18, 30): first GCD(12, 18) = 6, then GCD(6, 30) = 6. And LCM(12, 18, 30): first LCM(12, 18) = 36, then LCM(36, 30) = 180.

GCD & LCM Calculator — Free Online Calculator | LazyTools

Free Math Tool · Number Theory · Step-by-step

GCD & LCM Calculator

Find the greatest common divisor (GCD) and least common multiple (LCM) of up to 10 numbers instantly. See full step-by-step working for both the prime factorization method and the Euclidean algorithm. Includes fraction LCD helper and event scheduling sync tool.

Enter up to 10 positive integers

GCD — Greatest Common Divisor —

LCM — Least Common Multiple —

Enter numbers above to see steps.

What do these results mean?

Enter 2 to 4 fractions. The calculator finds the LCD (lowest common denominator) and rewrites each fraction with that denominator, then shows the simplified sum.

Results

Enter fractions above.

Enter how often each event repeats. The LCM tells you when all events next occur at the same time — useful for scheduling buses, medication doses, production cycles and more.

📐 Up to 10 numbers 📊 Prime factorization steps 🔢 Euclidean algorithm steps 🔵 Venn diagram (2 numbers) ➗ Fraction LCD helper 📅 Event sync / scheduling

How to Use the GCD and LCM Calculator

All three modes update in real time as you type. Furthermore, no Calculate button is needed — the results, steps and diagrams refresh automatically. Additionally, you can switch between the GCD & LCM, Fraction LCD and Event Sync tabs at any time.

Enter your numbersType a positive integer in each number box. Furthermore, click the plus button to add more numbers — up to ten in total. Additionally, hover any number box to reveal a red remove button if you want to reduce the count. The results update with every keystroke.
Read GCD and LCMThe green card shows the GCD and the blue card shows the LCM. Furthermore, the sub-label confirms what each result means in plain English. Additionally, for two numbers, the calculator shows the relationship GCD × LCM = a × b for verification.
Open the step-by-step accordionsClick the Prime Factorization accordion to see each number decomposed into prime powers. Furthermore, the calculator highlights which powers contribute to the GCD (minimum) and LCM (maximum). Additionally, open the Euclidean Algorithm accordion to trace each division step used to find the GCD.
View the Venn diagram (two numbers)When exactly two numbers are entered, a prime factor Venn diagram appears. Furthermore, the left circle shows prime factors unique to the first number, the overlap shows shared factors (the GCD components), and the right circle shows factors unique to the second number. Additionally, the product of all factors in both circles equals the LCM.
Use Fraction LCD and Event SyncSwitch to Fraction LCD to find the lowest common denominator for adding fractions. Furthermore, it rewrites each fraction and shows the simplified sum. Additionally, Event Sync uses LCM to show when repeating events — like buses or medication schedules — next coincide.

What Is the Greatest Common Divisor (GCD)?

The GCD of two or more integers is the largest positive integer that divides each of them exactly. Furthermore, it is also called the greatest common factor (GCF) or highest common factor (HCF). Additionally, finding the GCD is the first step in simplifying fractions, ratios and algebraic expressions.

For example, GCD(12, 18) = 6. Furthermore, 6 divides both 12 and 18 exactly, and no integer larger than 6 does the same. Additionally, the complete list of common divisors of 12 and 18 is 1, 2, 3 and 6 — and the greatest of those is 6. The GCD is always at least 1, since 1 divides every integer.

GCD is closely related to prime factorization. Furthermore, once you write each number as a product of prime powers, the GCD is the product of the shared primes raised to their minimum powers. Additionally, for 12 = 2² × 3 and 18 = 2 × 3², the shared primes are 2¹ and 3¹, so GCD = 2 × 3 = 6.

How to Calculate GCD — The Euclidean Algorithm

The Euclidean algorithm is the most efficient method for computing GCD, especially for large numbers. Furthermore, it avoids prime factorization entirely by using repeated division with remainders. Additionally, it runs in a number of steps proportional to the number of digits in the inputs — making it extremely fast even for very large integers.

The algorithm works as follows. Furthermore, to compute GCD(a, b), divide a by b to get remainder r. Then replace a with b and b with r. Additionally, repeat until the remainder is 0. The last non-zero remainder is the GCD.

GCD(48, 18): 48 = 2 × 18 + 12 → remainder 12 18 = 1 × 12 + 6 → remainder 6 12 = 2 × 6 + 0 → remainder 0 ∴ GCD(48, 18) = 6

The algorithm is named after the ancient Greek mathematician Euclid, who described it in Elements around 300 BCE. Furthermore, it is one of the oldest known algorithms still in widespread use. Additionally, modern computer implementations use modular arithmetic, so the step a mod b replaces the explicit division and subtraction.

What Is the Least Common Multiple (LCM)?

The LCM of two or more positive integers is the smallest positive integer that all the given numbers divide into exactly. Furthermore, it is also called the lowest common multiple or smallest common multiple. Additionally, LCM is the basis for finding the lowest common denominator when adding or subtracting fractions.

For example, LCM(4, 6) = 12. Furthermore, the multiples of 4 are 4, 8, 12, 16, 20... and the multiples of 6 are 6, 12, 18, 24... Additionally, the first number that appears in both lists is 12, which makes it the least common multiple. The LCM is always at least as large as the greatest of the input numbers.

For two numbers, the fastest way to compute LCM uses the GCD. Furthermore, LCM(a, b) = (a × b) / GCD(a, b). Additionally, computing the GCD first via the Euclidean algorithm prevents overflow, because dividing by GCD before multiplying keeps the numbers smaller. For example: LCM(12, 18) = (12 × 18) / 6 = 216 / 6 = 36.

Prime Factorization Method for LCM and GCD

The prime factorization method decomposes each number into its prime factors, then applies simple rules. Furthermore, it is the most educational method because it shows exactly which primes contribute to each result. Additionally, the method works well for small numbers and helps students understand why GCD and LCM have their values.

Find the prime factorization of each numberUse trial division to express each number as a product of prime powers. Furthermore, for 12: 12 = 4 × 3 = 2² × 3. For 18: 18 = 2 × 9 = 2 × 3². Additionally, for 30: 30 = 2 × 15 = 2 × 3 × 5. Each prime is written with its exponent.
List all primes that appear in any numberCollect every distinct prime across all numbers. Furthermore, for 12, 18 and 30, the primes are 2, 3 and 5. Additionally, write them as columns in a table alongside the exponent they appear with in each number. A prime that does not appear in a number gets exponent 0.
Compute GCD — take minimum exponentsFor each prime, take the smallest exponent it appears with across all numbers. Furthermore, for prime 2: exponents are 2, 1, 1 — minimum is 1. For prime 3: exponents are 1, 2, 1 — minimum is 1. Additionally, for prime 5: exponents are 0, 0, 1 — minimum is 0 (5 does not appear in GCD). GCD = 2¹ × 3¹ = 6.
Compute LCM — take maximum exponentsFor each prime, take the largest exponent it appears with across all numbers. Furthermore, for prime 2: maximum is 2. For prime 3: maximum is 2. Additionally, for prime 5: maximum is 1. LCM = 2² × 3² × 5¹ = 4 × 9 × 5 = 180.

The Relationship Between GCD and LCM

For any two positive integers a and b, GCD(a, b) × LCM(a, b) = a × b. Furthermore, this elegant identity connects the two operations and provides a fast way to find one from the other. Additionally, the calculator shows this verification in the results panel for two-number inputs.

GCD(a, b) × LCM(a, b) = a × b Example: GCD(12, 18) = 6, LCM(12, 18) = 36 Check: 6 × 36 = 216 = 12 × 18 ✓

This identity does not extend directly to three or more numbers. Furthermore, for three numbers, GCD(a,b,c) × LCM(a,b,c) does not generally equal a × b × c. Additionally, the correct multi-number approach applies the two-number formula iteratively: GCD(a,b,c) = GCD(GCD(a,b), c) and LCM(a,b,c) = LCM(LCM(a,b), c).

GCD divides LCM

The GCD of any set of numbers always divides their LCM exactly. Furthermore, this is because the LCM contains at least the prime powers present in the GCD. Additionally, if GCD = 6 and LCM = 180, then 180 / 6 = 30 — an exact division confirming the relationship.

Coprime numbers (GCD = 1)

Two numbers are coprime — also called relatively prime — when their GCD is 1. Furthermore, for coprime numbers, LCM(a, b) = a × b, because they share no prime factors. Additionally, consecutive integers are always coprime: GCD(n, n+1) = 1 for all positive integers n.

Real-World Applications of GCD and LCM

GCD and LCM appear throughout mathematics, engineering and everyday life. Furthermore, understanding them unlocks faster solutions to fraction arithmetic, scheduling problems and resource allocation tasks. Additionally, many problems that seem unrelated to number theory are actually LCM or GCD problems in disguise.

🍎 Simplifying fractions

To reduce a fraction to lowest terms, divide numerator and denominator by their GCD. Furthermore, 12/18 ÷ GCD(12,18) = 12/18 ÷ 6 = 2/3. Additionally, this is why GCD is also called the greatest common factor — it factors out of both parts of the fraction.

➕ Adding fractions

Adding fractions with different denominators requires a common denominator. Furthermore, the best choice is the LCD — the least common denominator — which equals LCM(denominator1, denominator2). Additionally, using the LCM rather than the product of the denominators keeps the numbers as small as possible.

🚌 Bus and event scheduling

If Bus A departs every 12 minutes and Bus B every 18 minutes, LCM(12, 18) = 36 tells you they next depart together in 36 minutes. Furthermore, the same logic applies to shift patterns, production cycles and any repeating event. Additionally, the Event Sync tab above calculates this automatically with a visual timeline.

🎁 Dividing into equal groups

If you have 24 apples and 36 oranges and want identical gift bags with no leftovers, GCD(24, 36) = 12 means you can make exactly 12 bags. Furthermore, each bag gets 24/12 = 2 apples and 36/12 = 3 oranges. Additionally, GCD gives the maximum number of equal groups in this type of problem.

📐 Simplifying ratios

A ratio 24:36 simplifies to 2:3 by dividing both parts by GCD(24, 36) = 12. Furthermore, this is exactly the same operation as simplifying a fraction. Additionally, simplified ratios are more readable and easier to work with in recipes, scale drawings and financial comparisons.

⚙️ Gear ratios and cycles

In mechanical engineering, LCM determines when gears return to their starting positions. Furthermore, two gears with 12 and 18 teeth align at starting position every LCM(12, 18) = 36 teeth of rotation. Additionally, this is used in clock mechanisms, conveyor belt design and synchronous motor calculations.

GCD and LCM with More Than Two Numbers

Finding GCD and LCM for three or more numbers uses the same algorithms applied iteratively. Furthermore, the key identity is that both operations are associative: GCD(a, b, c) = GCD(GCD(a, b), c) and LCM(a, b, c) = LCM(LCM(a, b), c). Additionally, this means any multi-number problem reduces to a sequence of two-number problems.

For example, to find GCD(12, 18, 30). Furthermore, compute GCD(12, 18) = 6 first. Then compute GCD(6, 30) = 6. Additionally, the final answer is 6. For LCM(12, 18, 30): compute LCM(12, 18) = 36, then LCM(36, 30) = 180. The step-by-step accordion above shows each iteration for whatever numbers you enter.

An alternative multi-number approach uses the division table method. Furthermore, write all numbers in a row, then find a prime that divides at least one of them. Divide those numbers and carry the rest unchanged. Additionally, repeat with the resulting row until all values reduce to 1. The product of all the dividing primes equals the LCM.

Common Mistakes When Calculating GCD and LCM

Several errors appear consistently when students first learn these calculations. Furthermore, recognising them in advance prevents careless mistakes in exams and homework. Additionally, the step-by-step display in this calculator is designed to catch each of these errors explicitly.

Confusing minimum and maximum powers

For GCD, take minimum prime powers. For LCM, take maximum prime powers. Furthermore, swapping these gives the wrong answer in both cases. Additionally, a useful memory aid: GCD is the smaller of the two results, so it uses smaller (minimum) powers; LCM is the larger result, so it uses larger (maximum) powers.

Using product instead of LCM for fractions

Adding 1/4 + 1/6 does NOT require denominator 24 (4 × 6). Furthermore, the correct denominator is LCM(4, 6) = 12. Additionally, using the product instead of the LCM gives a correct but unreduced fraction, requiring an extra simplification step. Always use LCM for the common denominator.

Forgetting to include all prime factors

A prime that appears in only one of the numbers still contributes to the LCM. Furthermore, it is easy to overlook a prime factor in the larger number. Additionally, the prime factorization accordion in this calculator lists every prime that appears in any number, preventing omissions.

Applying the GCD × LCM = a × b identity to three numbers

The identity GCD × LCM = a × b applies only to exactly two numbers. Furthermore, for three numbers a, b, c — the identity GCD(a,b,c) × LCM(a,b,c) does not equal a × b × c in general. Additionally, always use the iterative two-number approach for three or more inputs.

Frequently Asked Questions

The GCD is the largest integer that divides all given numbers exactly. Furthermore, the LCM is the smallest positive integer that all given numbers divide into exactly. Additionally, GCD answers "what is the biggest number that fits into all of these?" while LCM answers "what is the smallest number that all of these fit into?"

Divide a by b to get remainder r. Furthermore, replace a with b and b with r. Repeat until b reaches 0. Additionally, the GCD is the last non-zero remainder. For GCD(48, 18): 48 = 2×18+12, then 18 = 1×12+6, then 12 = 2×6+0. Therefore GCD = 6.

For two numbers, GCD(a, b) × LCM(a, b) = a × b. Furthermore, this means LCM(a, b) = (a × b) / GCD(a, b). Additionally, this identity does not extend to three or more numbers — use iterative application of the two-number formula instead.

Write each number as a product of prime powers. Furthermore, for each prime that appears in any number, take the highest power it appears with. Additionally, multiply these highest powers together. For LCM(12, 18): 12 = 2² × 3 and 18 = 2 × 3², so LCM = 2² × 3² = 4 × 9 = 36.

No. Furthermore, the GCD of any set of numbers is always less than or equal to the smallest number in that set. Additionally, a divisor of a number can never exceed the number itself, so GCD is bounded by the smallest input. GCD is always at least 1.

GCD simplifies fractions: divide numerator and denominator by GCD to reduce to lowest terms. Furthermore, it divides items into the maximum number of equal groups without leftovers. Additionally, it simplifies ratios and helps factor out the common part of two algebraic expressions.

LCM is the lowest common denominator for adding fractions. Furthermore, it solves scheduling and synchronization problems — such as when two buses next depart together. Additionally, it synchronizes repeating cycles in engineering: gear teeth, signal frequencies and production run lengths.

Apply the two-number algorithm iteratively. Furthermore, GCD(a, b, c) = GCD(GCD(a, b), c). Additionally, LCM(a, b, c) = LCM(LCM(a, b), c). For example, GCD(12, 18, 30) = GCD(GCD(12,18), 30) = GCD(6, 30) = 6.

Two numbers are coprime (or relatively prime) when their GCD is 1. Furthermore, they share no prime factors. Additionally, for coprime numbers, LCM(a, b) = a × b exactly. Consecutive integers are always coprime: GCD(n, n+1) = 1 for all positive integers n.

Rate this tool

4.2

out of 5

★★★★★

317 ratings

5 ★

59%

4 ★

21%

3 ★

2 ★

1 ★

10%

How useful was this tool?

★ ★ ★ ★ ★

Rate this tool

4.2

out of 5

★★★★★

317 ratings

5 ★

59%

4 ★

21%

3 ★

2 ★

1 ★

10%

How useful was this tool?

★ ★ ★ ★ ★

GCD & LCM Calculator

How to Use the GCD and LCM Calculator

What Is the Greatest Common Divisor (GCD)?

How to Calculate GCD — The Euclidean Algorithm

What Is the Least Common Multiple (LCM)?

Prime Factorization Method for LCM and GCD

The Relationship Between GCD and LCM

GCD divides LCM

Coprime numbers (GCD = 1)

Real-World Applications of GCD and LCM

🍎 Simplifying fractions

➕ Adding fractions

🚌 Bus and event scheduling

🎁 Dividing into equal groups

📐 Simplifying ratios

⚙️ Gear ratios and cycles

GCD and LCM with More Than Two Numbers

Common Mistakes When Calculating GCD and LCM

Confusing minimum and maximum powers

Using product instead of LCM for fractions

Forgetting to include all prime factors

Applying the GCD × LCM = a × b identity to three numbers

Frequently Asked Questions

Related Math and Science Tools

Prime Factorization Calculator

Fraction Calculator

Percentage Calculator

Factor Calculator

Modulo Calculator

Ratio Simplifier

Rate this tool

Rate this tool