What is the Euclidean algorithm?

An ancient, highly efficient algorithm for finding GCD, attributed to Euclid around 300 BC. It uses the property GCD(a, b) = GCD(b, a mod b), applied repeatedly until one term is zero. It runs in logarithmic time and is still the fastest known method for GCD — a genuinely timeless piece of mathematics.

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

It is a classical theorem of number theory: every prime factor of a × b appears in either LCM or GCD (but not duplicated), because GCD captures the shared factors and LCM captures the union. The identity fails for three or more numbers — LCM(a, b, c) × GCD(a, b, c) is not generally equal to a × b × c.

How are GCD and LCM used with fractions?

GCD simplifies a fraction by dividing numerator and denominator by their GCD. LCM of the denominators gives the least common denominator when adding or subtracting fractions. Both operations are essential in fraction arithmetic and why these concepts are taught early in school mathematics.

What is the GCD of 0 and n?

GCD(0, n) = n for any positive n, because every positive integer divides 0 and n divides itself. GCD(0, 0) is mathematically undefined — there is no largest integer that divides zero by any reasonable definition, although some software returns 0 by convention.

Can I enter negative numbers?

GCD and LCM are traditionally defined for positive integers, so this calculator takes the absolute values of any negative inputs. GCD(-12, 18) is treated as GCD(12, 18) = 6. The sign of the inputs does not affect divisibility relationships.

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

Scheduling (when will repeating events coincide?), music theory (finding rhythmic patterns), cryptography (RSA and modular arithmetic rely on GCD), engineering (gear design), and manufacturing (batch sizing). Almost anything involving cycles or divisibility benefits from these tools.

How fast is the Euclidean algorithm for very large numbers?

Extremely fast — it runs in O(log(min(a, b))) time. Even for 300-digit numbers used in cryptography, GCD takes microseconds. This speed is one reason why the algorithm has survived 2,300 years essentially unchanged.

LCM / GCD Calculator

Math

Calculate Least Common Multiple and Greatest Common Divisor of integers.

Math

LCM / GCD Calculator

Generated on April 24, 2026

Numbers (comma or space separated, integers only)

?What is the LCM / GCD Calculator?

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.

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.

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. GCD (Greatest Common Divisor) and HCF (Highest Common Factor) are two names for the same concept. American textbooks often say GCD; British and Pakistani textbooks often say HCF. The value is identical — just different terminology.

GPA Calculator

Calculate your Grade Point Average on the 4.0 scale from your courses.

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.

LCM / GCD Calculator

LCM / GCD Calculator

?What is the LCM / GCD Calculator?

The Formula

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?

Explore More Tools