GCF / GCD and LCM Calculator with Steps
Find the greatest common factor (greatest common divisor) and the least common multiple of 2 to 20 integers, with Euclid’s successive divisions and prime factorizations.
2 to 20 integers, separated by commas, semicolons or spaces.
The GCD is 1: these numbers are coprime (relatively prime). A fraction made of two of them is therefore in simplest form.
Euclidean algorithm
Prime factorization
Was this tool useful?
How does this tool work?
This calculator finds the GCD (greatest common divisor, also known as GCF or HCF) and the LCM (least common multiple) of two to twenty integers. It shows the successive divisions of the Euclidean algorithm and the prime factorization of each number, so you can understand the result and write it down in your work. Calculations are exact, even with numbers of dozens of digits.
The GCD of several integers is the largest integer that divides all of them. The LCM is the smallest positive integer that is a multiple of each of them. For example, GCD(12, 18) = 6 and LCM(12, 18) = 36.
The Euclidean algorithm relies on a simple property: the GCD of a and b equals the GCD of b and the remainder of the division of a by b. The pair (a, b) is therefore replaced by (b, r) until the remainder is zero; the last non-zero remainder is the GCD. The method already appears in Euclid’s Elements, Book VII, and remains one of the fastest known.
For more than two numbers, the calculation is applied step by step: GCD(a, b, c) = GCD(GCD(a, b), c). The same goes for the LCM.
Prime factorization gives a second method: the GCD is the product of the prime factors common to all the numbers, each with its smallest exponent, and the LCM is the product of all the prime factors found, each with its largest exponent. For two numbers, the product a × b always equals GCD × LCM.
Two numbers whose GCD is 1 are called coprime (or relatively prime): they have no common divisor other than 1, even if they are not prime themselves (8 and 15, for example).
How to use this tool
Enter the numbers
Type 2 to 20 integers separated by commas, semicolons or spaces.
Read the GCD and the LCM
Both results appear instantly, with a note if the numbers are coprime.
Follow Euclid’s divisions
Each line a = q × b + r shows one division with remainder, down to a zero remainder.
Compare with the prime factors
The factorization of each number, of the GCD and of the LCM lets you check the calculation with a second method.
GCD and LCM formulas
Euclid’s property
GCD(a, b) = GCD(b, r), where a = q × b + r and 0 ≤ r < b
Relation between GCD and LCM
GCD(a, b) × LCM(a, b) = a × b
Several numbers
GCD(a, b, c) = GCD(GCD(a, b), c)
Using prime factors
GCD = ∏ p^min(exponents) ; LCM = ∏ p^max(exponents)
- a, b, c
- the integers being studied
- q, r
- quotient and remainder of the division of a by b
- p
- prime number appearing in a factorization
Use cases
Simplify a fraction
Dividing the numerator and the denominator by their GCD gives the fraction in simplest form directly.
Add fractions
The LCM of the denominators is the least common denominator.
Sharing and scheduling problems
The GCD answers questions about the largest possible equal shares, the LCM questions about events that recur together (two buses, two gears, two blinking lights).
Arithmetic and computing
The GCD is used to check that two numbers are coprime, a notion used in cryptography (RSA) and number theory.
Examples
GCD of two numbers
252 = 2 × 105 + 42, then 105 = 2 × 42 + 21, then 42 = 2 × 21 + 0: the last non-zero remainder is 21.
Input
252 and 105Result
GCD = 21LCM for a common denominator
6 = 2 × 3, 8 = 2³ and 10 = 2 × 5: LCM = 2³ × 3 × 5 = 120, the least common denominator of 1/6, 1/8 and 1/10.
Input
6, 8 and 10Result
LCM = 120Coprime numbers
No common prime factor: their LCM is simply their product.
Input
8 and 15Result
GCD = 1, LCM = 120Sharing problem
With 84 red marbles, 126 blue and 210 green, you can make at most 42 identical bags of 2 red, 3 blue and 5 green.
Input
84, 126 and 210Result
GCD = 42Tips and best practices
- The GCD is always less than or equal to the smallest of the numbers, and the LCM always greater than or equal to the largest.
- If one number divides all the others, it is their GCD; if one number is a multiple of all the others, it is their LCM.
- For two numbers, compute the LCM from the GCD: LCM(a, b) = a × b ÷ GCD(a, b).
- Signs have no effect: the GCD and the LCM are given for the absolute values of the numbers entered.
- With a 0 among the numbers, the GCD is that of the other numbers and the LCM is 0.
Sources and references
- Weisstein E.W., Greatest Common Divisor (opens in a new tab), Wolfram MathWorldPage in English
- Weisstein E.W., Least Common Multiple (opens in a new tab), Wolfram MathWorldPage in English
- Weisstein E.W., Euclidean Algorithm (opens in a new tab), Wolfram MathWorldPage in English
- Euclid, ed. D.E. Joyce, Elements, Book VII, Proposition 2 (opens in a new tab), Clark UniversityPage in English
- Weisstein E.W., Prime Factorization (opens in a new tab), Wolfram MathWorldPage in English
Frequently asked questions
How do you find the GCD (GCF) of two numbers?
Use the Euclidean algorithm: divide the larger number by the smaller, replace the pair by (divisor, remainder) and repeat until the remainder is zero. The last non-zero remainder is the GCD. Example: 252 = 2 × 105 + 42, 105 = 2 × 42 + 21, 42 = 2 × 21 + 0, so GCD(252, 105) = 21.
How do you find the LCM of two numbers?
The fastest way is the relation LCM(a, b) = a × b ÷ GCD(a, b). For 12 and 18: 12 × 18 = 216 and 216 ÷ 6 = 36. You can also take all the prime factors with their largest exponent: 12 = 2² × 3 and 18 = 2 × 3², so LCM = 2² × 3² = 36.
What is the difference between GCD and LCM?
The GCD is the greatest common divisor: it is smaller than the starting numbers and is used for sharing or simplifying. The LCM is the least common multiple: it is larger than the starting numbers and is used to find a common denominator or a common period.
What does “coprime numbers” mean?
Two integers are coprime (relatively prime) when their GCD is 1. They need not be prime themselves: 8 and 15 are coprime although neither 8 nor 15 is a prime number. The fraction 8/15 is therefore in simplest form.
How do you find the GCD of three or more numbers?
Work step by step: GCD(a, b, c) = GCD(GCD(a, b), c). The tool shows each step. The method is the same for the LCM.
Can the GCD be equal to one of the numbers?
Yes, when that number divides all the others. For example, GCD(15, 45, 60) = 15. Likewise, the LCM equals one of the numbers when it is a multiple of all the others.
How large can the numbers be?
The GCD and the LCM are computed exactly whatever the size of the numbers. The prime factorization is displayed up to 10¹⁵; beyond that it would be too slow to compute in the browser.
Related tools
Keep going with these tools
Tools similar or complementary to this one.
Similar tools
Add, subtract, multiply, divide and simplify fractions, with every step shown.
Mathematics & calculationNewFeaturedUse this tool
Find a fourth proportional by cross multiplication, solve inverse proportion, or simplify a ratio.
Mathematics & calculationNewUse this tool
Convert an integer between bases 2 and 36: binary, octal, decimal, hexadecimal or a custom base, with negatives and very large integers.
Mathematics & calculationUse this tool