What is GCD (Greatest Common Divisor)?

GCD is the largest positive integer that divides both numbers evenly without a remainder. For example, GCD of 12 and 18 is 6, because 6 is the largest number that divides both 12 and 18 evenly.

What is LCM (Least Common Multiple)?

LCM is the smallest positive integer that is a multiple of both numbers. For example, LCM of 4 and 6 is 12, because 12 is the smallest number that is divisible by both 4 and 6.

How are GCD and LCM related?

GCD and LCM are related by the formula: GCD(a, b) × LCM(a, b) = a × b. This means if you know one, you can calculate the other. For example, if GCD(12, 18) = 6, then LCM(12, 18) = (12 × 18) / 6 = 36.

What is the Euclidean algorithm?

The Euclidean algorithm is an efficient method to find GCD. It repeatedly applies: GCD(a, b) = GCD(b, a mod b) until b becomes 0, then a is the GCD. This is much faster than listing all divisors.

When are GCD and LCM used?

GCD is used to simplify fractions (dividing numerator and denominator by GCD), while LCM is used to find common denominators for adding/subtracting fractions. Both are fundamental in number theory and algebra.

Can GCD or LCM be zero?

GCD cannot be zero (by definition, it's the greatest positive divisor). LCM can be zero only if both numbers are zero, but typically we work with positive integers where LCM is always positive.

GCD & LCM Calculator

Find the greatest common divisor and least common multiple of two numbers. Calculate GCD and LCM instantly using the Euclidean algorithm.

GCD & LCM

Result

Greatest Common Divisor (GCD): 0
Least Common Multiple (LCM): 0

Formula & Guide

GCD

GCD (Euclidean Algorithm)

GCD(a, b) = GCD(b, a mod b)

Recursive formula until remainder is 0

LCM

LCM Formula

LCM(a, b) = (a × b) / GCD(a, b)

Product divided by GCD

=

Relationship

GCD × LCM = a × b

Product of GCD and LCM equals product of numbers

Formula Variables

a, b

Numbers

The two positive integers to find GCD and LCM for

GCD

Greatest Common Divisor

The largest positive integer that divides both a and b evenly

LCM

Least Common Multiple

The smallest positive integer that is divisible by both a and b

mod

Modulo

The remainder after division (a mod b = remainder of a ÷ b)

Step-by-Step Scenario

Example Scenario

Number 1

48

Number 2

18

1

Apply Euclidean Algorithm

GCD(48, 18) = GCD(18, 48 mod 18)
48 mod 18 = 12 (remainder)

Divide 48 by 18, use the remainder

2

Continue the Algorithm

GCD(18, 12) = GCD(12, 18 mod 12)
18 mod 12 = 6

3

Final Step

GCD(12, 6) = GCD(6, 12 mod 6)
12 mod 6 = 0

GCD(48, 18) = 6

4

Calculate LCM

LCM(48, 18) = (48 × 18) / GCD(48, 18)
LCM(48, 18) = 864 / 6

LCM(48, 18) = 144

Additional Examples

Small Numbers

Numbers: 12 and 8

GCD

GCD(12, 8) = 4

LCM

LCM(12, 8) = 24

Prime Numbers

Numbers: 7 and 11

GCD

GCD(7, 11) = 1 (coprime)

LCM

LCM(7, 11) = 77

Characteristics of GCD & LCM

Efficient Algorithm

The Euclidean algorithm for GCD is very efficient, with time complexity O(log min(a,b)), making it fast even for large numbers.

Fraction Simplification

GCD is used to simplify fractions by dividing numerator and denominator by their GCD. For example, 12/18 simplifies to 2/3 using GCD(12,18)=6.

Common Denominators

LCM is essential for finding common denominators when adding or subtracting fractions. For example, to add 1/4 + 1/6, use LCM(4,6)=12.

Mathematical Relationship

GCD and LCM are inversely related: GCD × LCM = a × b. This relationship allows calculating one from the other.

Important Notes

GCD is always positive and cannot be zero. The GCD of any number and 0 is the absolute value of that number.
LCM is always positive (for positive inputs) and is at least as large as the larger of the two numbers.
If two numbers are coprime (GCD = 1), their LCM is simply their product: LCM(a, b) = a × b when GCD(a, b) = 1.
The Euclidean algorithm is much more efficient than listing all divisors, especially for large numbers.
GCD and LCM are fundamental in number theory and are used extensively in algebra, cryptography, and computer science.

Frequently Asked Questions

Find answers to common questions about GCD and LCM calculations.