What is the Euclidean algorithm?

An ancient, ridiculously efficient way to find GCD, attributed to Euclid around 300 BC. The trick: GCD(a, b) equals GCD(b, a mod b), applied over and over until one of them hits zero. It runs in logarithmic time and is still the fastest known method for finding GCD — a piece of math that has survived 2,300 years essentially unchanged because nobody's improved on it.

Why does LCM × GCD equal the product a × b?

Classical number theory result: every prime factor of a × b shows up in either the GCD or the LCM but never both, because GCD captures the shared factors and LCM captures the union. The two products together account for everything. Worth knowing: this identity only works for two numbers — for three or more, LCM(a, b, c) × GCD(a, b, c) is generally not a × b × c.

How are GCD and LCM used with fractions?

GCD simplifies a fraction — divide top and bottom by their GCD to get lowest terms. LCM finds the least common denominator when you need to add or subtract fractions with different denominators. These two operations together are why GCD and LCM get drilled into students so early in school math — fractions don't work without them.

What is the GCD of 0 and n?

GCD(0, n) is just n for any positive n, because every positive integer divides 0 cleanly, and n divides itself. GCD(0, 0) is undefined — there's no 'largest' integer that divides zero, since every integer does. Some software returns 0 by convention to avoid crashing, but mathematically that's a fudge.

Can I enter negative numbers?

GCD and LCM are traditionally defined for positive integers only, so this calculator just takes the absolute values if you enter negatives. GCD(-12, 18) gets treated as GCD(12, 18) = 6. Signs don't affect divisibility — whether a number is positive or negative, the same integers divide into it.

What is the GCD and LCM used for in real applications?

Scheduling (when will three repeating events coincide?), music theory (finding rhythmic patterns), cryptography (RSA and modular arithmetic both lean heavily on GCD), engineering (gear ratio design), manufacturing (batch sizing), and competitive programming. Anywhere cycles or divisibility show up, GCD and LCM are quietly doing work in the background.

How fast is the Euclidean algorithm for very large numbers?

Absurdly fast — O(log(min(a, b))) time complexity. Even for the 300-digit numbers used in RSA cryptography, GCD takes microseconds on a phone. That speed is exactly why nobody has bothered to invent anything better in 2,300 years; Euclid's algorithm is essentially optimal for the problem.

Premium Converters

LCM / GCD Calculator

Math

Find the LCM and GCD (HCF) of two or more integers using the Euclidean algorithm — useful for simplifying fractions, finding common denominators, and scheduling repeating events.

Math

LCM / GCD Calculator

Generated on May 23, 2026

Numbers (comma or space separated, integers only)

Quick Answer

Find the LCM and GCD (HCF) of two or more integers using the Euclidean algorithm — useful for simplifying fractions, finding common denominators, and scheduling repeating events.

Overview — LCM / GCD Calculator

Math

This calculator finds both the Greatest Common Divisor (GCD, also called Highest Common Factor or HCF) and the Least Common Multiple (LCM) of any list of positive integers. GCD is the largest integer that divides every value in your list; LCM is the smallest positive integer that every value divides into. These are essential for simplifying fractions (GCD of numerator and denominator), adding or subtracting fractions (LCM of denominators), scheduling repeating events, and many number-theory problems in competitive mathematics and cryptography.

Formula

GCD via the Euclidean algorithm: GCD(a, b) = GCD(b, a mod b), repeated until b = 0. LCM identity: LCM(a, b) = |a × b| ÷ GCD(a, b). For more than two numbers, apply pairwise — the operation is associative.

GCD simplifies fractions; LCM finds the least common denominator for adding them — the two most useful applications.

Identity: LCM(a,b) × GCD(a,b) = a × b (only works for two numbers).

GCD and HCF are two names for the same concept — US uses GCD, UK/Pakistan uses HCF.

By Muhammad Salman SaleemUpdated: May 23, 2026MethodologyFree, no sign-upRuns in your browser — your data stays private

From the editors — what to know before you start

Class IX or X, your math teacher wrote 'find HCF and LCM of 36 and 48' on the board, and you stared at the page wondering how anyone is supposed to find divisors of 48 in their head. Most students learn this with prime factorization (which works but is tedious), never meeting the Euclidean algorithm — which is faster, older than the Quran, and a genuinely beautiful piece of mathematics. Euclid's trick: keep replacing the larger number with the remainder when you divide, and within a handful of steps you've got the GCD. From there, LCM is just a × b divided by GCD. Practical uses go way beyond homework. Synchronizing traffic lights, finding when three repeating events coincide, simplifying fractions for an answer that won't lose marks, and — at the high end — securing every HTTPS connection you've ever made, because RSA encryption leans heavily on GCD properties of large primes. Real-world example: if you have lessons that repeat every 30, 45, and 60 minutes, they all coincide every LCM(30, 45, 60) = 180 minutes, or 3 hours. That's not a homework problem — that's exactly how rotation schedules at hospitals, schools, and factories get built. This calculator handles two or more inputs and shows both GCD (HCF) and LCM together, with the classical product identity (LCM × GCD = a × b) shown for verification.

Pro tips most people learn the hard way

GCD and HCF are the same thing — different name, identical math. American books say GCD, Pakistani and British books say HCF. If a board exam asks for HCF, run GCD; if a programming interview asks for GCD, run HCF. The 'two names' are just regional, and knowing both saves a moment of confusion.
Euclid's algorithm beats prime factorization for finding GCD, every time. Prime factorization scales badly — factoring large numbers is genuinely hard (RSA security depends on it). Euclid's algorithm runs in log time on inputs of any size and is what every programming language's gcd() function actually uses internally.
LCM × GCD = a × b is the verify-your-work shortcut for two-number problems. Compute one, then derive the other instead of solving from scratch. But this only works for two numbers — for three or more, you have to chain the operations pairwise, not try to apply the identity directly.
For fraction addition, find the LCM of the denominators and use it as the common denominator — that's the 'least common denominator.' Skipping this step (and just multiplying denominators together) works mathematically but gives you bigger numbers that need more simplification at the end. Save the work upfront.
Real-world LCM problems hide in scheduling — when do three rotating shifts coincide, when does the maintenance cycle align with the audit cycle, when do all the traffic lights at an intersection turn green together. If you ever schedule rotations, LCM is the math nobody tells you you're already doing in your head intuitively.

?What is the LCM / GCD Calculator?

The Formula

GCD via the Euclidean algorithm: GCD(a, b) = GCD(b, a mod b), repeated until b = 0. LCM identity: LCM(a, b) = |a × b| ÷ GCD(a, b). For more than two numbers, apply pairwise — the operation is associative.

Euclid's algorithm (published around 300 BC and still optimal for this problem) repeatedly replaces the pair (a, b) with (b, a mod b), shrinking the numbers rapidly. When b becomes 0, the remaining a is the GCD. The LCM follows from the beautiful identity LCM(a, b) × GCD(a, b) = a × b, which holds for all positive integers. For longer lists, just chain: GCD(a, b, c) = GCD(GCD(a, b), c). The same logic extends to LCM.

LCM & GCD Reference — Common Number Pairs

Precomputed LCM and GCD for commonly-asked integer pairs. Useful for fraction arithmetic, scheduling, and math homework.

Numbers	GCD / HCF	LCM	Product check (LCM × GCD)
4, 6	2	12	24 (= 4 × 6)
8, 12	4	24	96 (= 8 × 12)
12, 18	6	36	216 (= 12 × 18)
15, 25	5	75	375 (= 15 × 25)
18, 24	6	72	432 (= 18 × 24)
20, 30	10	60	600 (= 20 × 30)
24, 36	12	72	864 (= 24 × 36)
25, 40	5	200	1,000 (= 25 × 40)
36, 48	12	144	1,728 (= 36 × 48)
60, 72	12	360	4,320 (= 60 × 72)
100, 150	50	300	15,000 (= 100 × 150)

Put It in Perspective

GCD simplifies fractions; LCM finds the least common denominator for adding them — the two most useful applications.

Identity: LCM(a,b) × GCD(a,b) = a × b (only works for two numbers).

GCD and HCF are two names for the same concept — US uses GCD, UK/Pakistan uses HCF.

Euclid's algorithm (300 BC) for GCD is still the fastest known method — unchanged for 2,300 years.

Practical Examples

12 and 18: GCD = 6, LCM = 36 — classic textbook example that also shows the identity 12 × 18 = 216 = 6 × 36.

8 and 12: GCD = 4, LCM = 24 — useful when simplifying 8/12 or finding a common denominator.

4, 6, and 10: GCD = 2, LCM = 60 — the minimum time at which three repeating events (every 4, 6, and 10 units) coincide.

Adding fractions: to add 1/4 + 1/6 + 1/10, the LCM of denominators (60) becomes the least common denominator.

Gear ratios: a gear with 24 teeth meshing with one of 36 teeth will return to the same relative position after LCM(24, 36) = 72 teeth of rotation.

Traffic lights: if three signals cycle every 30, 45, and 60 seconds, they synchronize every LCM(30, 45, 60) = 180 seconds (3 minutes).

Frequently Asked Questions

Yes — they're two names for the same thing. American textbooks tend to say GCD (Greatest Common Divisor); British and Pakistani textbooks usually say HCF (Highest Common Factor). The value is identical, the terminology is just regional. If your exam asks for HCF and you compute GCD, you've already got the right answer.

Popular Conversions

Jump to a ready-made conversion — useful for quick reference and sharing:

Browse all Math

GPA Calculator

Calculate your semester or cumulative Grade Point Average on the 4.0 scale, weighted by credit hours, with support for both weighted and unweighted grading systems.

Grade Calculator

Calculate your final grade from weighted categories like tests, homework, and exams.

Student Result Card Calculator

Subject-wise marks, grades, and a printable school result card — ideal for small schools and parents.

Fraction Calculator

Add, subtract, multiply, and divide proper, improper, and mixed fractions with automatic reduction to lowest terms and decimal equivalents for cooking, carpentry, and homework.

Ratio Calculator

Simplify ratios to lowest terms using GCD and solve proportions like a:b = c:x for any missing value — useful for recipes, map scales, aspect ratios, and mixing ingredients.

Average Calculator

Compute the arithmetic mean, median, mode, range, count, sum, minimum, and maximum from any list of numbers — essential for descriptive statistics, surveys, and grading.

Prime Number Checker

Test whether any integer is a prime number using trial division up to its square root, and view the complete unique prime factorization for composite numbers.

Scientific Calculator

Evaluate complex math expressions with trigonometric functions (sin, cos, tan), logarithms, exponents, square roots, parentheses, and constants like pi and e, following PEMDAS order.

Browse all Math calculators & converters

See every tool in this category, plus FAQs and category-specific guides.

Browse other categories

Islamic9 Financial14 Gold & Silver8 Health25 Unit19 Date & Time9 Construction22 Utility20 Fun12

Premium Converters

LCM / GCD Calculator

Math

Find the LCM and GCD (HCF) of two or more integers using the Euclidean algorithm — useful for simplifying fractions, finding common denominators, and scheduling repeating events.

Math

LCM / GCD Calculator

Generated on May 23, 2026

Numbers (comma or space separated, integers only)

Quick Answer

Find the LCM and GCD (HCF) of two or more integers using the Euclidean algorithm — useful for simplifying fractions, finding common denominators, and scheduling repeating events.

Overview — LCM / GCD Calculator

Math

Formula

GCD via the Euclidean algorithm: GCD(a, b) = GCD(b, a mod b), repeated until b = 0. LCM identity: LCM(a, b) = |a × b| ÷ GCD(a, b). For more than two numbers, apply pairwise — the operation is associative.

GCD simplifies fractions; LCM finds the least common denominator for adding them — the two most useful applications.

Identity: LCM(a,b) × GCD(a,b) = a × b (only works for two numbers).

GCD and HCF are two names for the same concept — US uses GCD, UK/Pakistan uses HCF.

By Muhammad Salman SaleemUpdated: May 23, 2026MethodologyFree, no sign-upRuns in your browser — your data stays private

From the editors — what to know before you start

Pro tips most people learn the hard way

GCD and HCF are the same thing — different name, identical math. American books say GCD, Pakistani and British books say HCF. If a board exam asks for HCF, run GCD; if a programming interview asks for GCD, run HCF. The 'two names' are just regional, and knowing both saves a moment of confusion.
Euclid's algorithm beats prime factorization for finding GCD, every time. Prime factorization scales badly — factoring large numbers is genuinely hard (RSA security depends on it). Euclid's algorithm runs in log time on inputs of any size and is what every programming language's gcd() function actually uses internally.
LCM × GCD = a × b is the verify-your-work shortcut for two-number problems. Compute one, then derive the other instead of solving from scratch. But this only works for two numbers — for three or more, you have to chain the operations pairwise, not try to apply the identity directly.
For fraction addition, find the LCM of the denominators and use it as the common denominator — that's the 'least common denominator.' Skipping this step (and just multiplying denominators together) works mathematically but gives you bigger numbers that need more simplification at the end. Save the work upfront.
Real-world LCM problems hide in scheduling — when do three rotating shifts coincide, when does the maintenance cycle align with the audit cycle, when do all the traffic lights at an intersection turn green together. If you ever schedule rotations, LCM is the math nobody tells you you're already doing in your head intuitively.

?What is the LCM / GCD Calculator?

The Formula

LCM & GCD Reference — Common Number Pairs

Precomputed LCM and GCD for commonly-asked integer pairs. Useful for fraction arithmetic, scheduling, and math homework.

Numbers	GCD / HCF	LCM	Product check (LCM × GCD)
4, 6	2	12	24 (= 4 × 6)
8, 12	4	24	96 (= 8 × 12)
12, 18	6	36	216 (= 12 × 18)
15, 25	5	75	375 (= 15 × 25)
18, 24	6	72	432 (= 18 × 24)
20, 30	10	60	600 (= 20 × 30)
24, 36	12	72	864 (= 24 × 36)
25, 40	5	200	1,000 (= 25 × 40)
36, 48	12	144	1,728 (= 36 × 48)
60, 72	12	360	4,320 (= 60 × 72)
100, 150	50	300	15,000 (= 100 × 150)

Put It in Perspective

GCD simplifies fractions; LCM finds the least common denominator for adding them — the two most useful applications.

Identity: LCM(a,b) × GCD(a,b) = a × b (only works for two numbers).

GCD and HCF are two names for the same concept — US uses GCD, UK/Pakistan uses HCF.

Euclid's algorithm (300 BC) for GCD is still the fastest known method — unchanged for 2,300 years.

Practical Examples

12 and 18: GCD = 6, LCM = 36 — classic textbook example that also shows the identity 12 × 18 = 216 = 6 × 36.

8 and 12: GCD = 4, LCM = 24 — useful when simplifying 8/12 or finding a common denominator.

4, 6, and 10: GCD = 2, LCM = 60 — the minimum time at which three repeating events (every 4, 6, and 10 units) coincide.

Adding fractions: to add 1/4 + 1/6 + 1/10, the LCM of denominators (60) becomes the least common denominator.

Gear ratios: a gear with 24 teeth meshing with one of 36 teeth will return to the same relative position after LCM(24, 36) = 72 teeth of rotation.

Traffic lights: if three signals cycle every 30, 45, and 60 seconds, they synchronize every LCM(30, 45, 60) = 180 seconds (3 minutes).

Frequently Asked Questions

Popular Conversions

Jump to a ready-made conversion — useful for quick reference and sharing:

Browse all Math

GPA Calculator

Calculate your semester or cumulative Grade Point Average on the 4.0 scale, weighted by credit hours, with support for both weighted and unweighted grading systems.

Grade Calculator

Calculate your final grade from weighted categories like tests, homework, and exams.

Student Result Card Calculator

Subject-wise marks, grades, and a printable school result card — ideal for small schools and parents.

Fraction Calculator

Add, subtract, multiply, and divide proper, improper, and mixed fractions with automatic reduction to lowest terms and decimal equivalents for cooking, carpentry, and homework.

Ratio Calculator

Simplify ratios to lowest terms using GCD and solve proportions like a:b = c:x for any missing value — useful for recipes, map scales, aspect ratios, and mixing ingredients.

Average Calculator

Compute the arithmetic mean, median, mode, range, count, sum, minimum, and maximum from any list of numbers — essential for descriptive statistics, surveys, and grading.

Prime Number Checker

Test whether any integer is a prime number using trial division up to its square root, and view the complete unique prime factorization for composite numbers.

Scientific Calculator

Evaluate complex math expressions with trigonometric functions (sin, cos, tan), logarithms, exponents, square roots, parentheses, and constants like pi and e, following PEMDAS order.

Browse all Math calculators & converters

See every tool in this category, plus FAQs and category-specific guides.

Browse other categories

Islamic9 Financial14 Gold & Silver8 Health25 Unit19 Date & Time9 Construction22 Utility20 Fun12

LCM / GCD Calculator — the LCM and GCD (HCF) of two or more integers using the… | Premium Converters

Premium Converters

Premium Converters

LCM / GCD Calculator

LCM / GCD Calculator

Overview — LCM / GCD Calculator

From the editors — what to know before you start

Pro tips most people learn the hard way

?What is the LCM / GCD Calculator?

The Formula

LCM & GCD Reference — Common Number Pairs

Put It in Perspective

Practical Examples

Frequently Asked Questions

Popular Conversions

Embed this calculator on your site

Browse other categories

Premium Converters

LCM / GCD Calculator

LCM / GCD Calculator

Overview — LCM / GCD Calculator

From the editors — what to know before you start

Pro tips most people learn the hard way

?What is the LCM / GCD Calculator?

The Formula

LCM & GCD Reference — Common Number Pairs

Put It in Perspective

Practical Examples

Frequently Asked Questions

Popular Conversions

Embed this calculator on your site

Browse other categories

Premium Converters

Premium Converters

LCM / GCD Calculator

LCM / GCD Calculator

Overview — LCM / GCD Calculator

From the editors — what to know before you start

Pro tips most people learn the hard way

?What is the LCM / GCD Calculator?

The Formula

LCM & GCD Reference — Common Number Pairs

Put It in Perspective

Practical Examples

Frequently Asked Questions

Is GCD the same as HCF?

What is the Euclidean algorithm?

Why does LCM × GCD equal the product a × b?

How are GCD and LCM used with fractions?

What is the GCD of 0 and n?

Can I enter negative numbers?

What is the GCD and LCM used for in real applications?

How fast is the Euclidean algorithm for very large numbers?

Popular Conversions

Embed this calculator on your site

More Math Tools

Browse other categories

Premium Converters

LCM / GCD Calculator

LCM / GCD Calculator

Overview — LCM / GCD Calculator

From the editors — what to know before you start

Pro tips most people learn the hard way

?What is the LCM / GCD Calculator?

The Formula

LCM & GCD Reference — Common Number Pairs

Put It in Perspective

Practical Examples

Frequently Asked Questions

Is GCD the same as HCF?

What is the Euclidean algorithm?

Why does LCM × GCD equal the product a × b?

How are GCD and LCM used with fractions?

What is the GCD of 0 and n?

Can I enter negative numbers?

What is the GCD and LCM used for in real applications?

How fast is the Euclidean algorithm for very large numbers?

Popular Conversions

Embed this calculator on your site

More Math Tools

Browse other categories