What are the GCD and the LCM?
The greatest common divisor (GCD, also called the highest common factor or HCF) of a set of integers is the largest positive integer that divides every number in the set without a remainder. The least common multiple (LCM) is the smallest positive integer that is divisible by every number in the set. The numbers 48 and 180 share the divisors 1, 2, 3, 4, 6 and 12, so gcd(48, 180) = 12, while their common multiples start at 720, so lcm(48, 180) = 720.
The GCD is used to reduce fractions to lowest terms and to decide whether two numbers are coprime. The LCM is what you need to add fractions with different denominators or to find when two repeating cycles line up again. Both appear throughout number theory and cryptography; for example, an RSA public exponent e must satisfy gcd(e, φ(n)) = 1.
How the calculator finds the GCD
The calculator uses Euclid's algorithm, which rests on the identity gcd(a, b) = gcd(b, a mod b). Divide the larger number by the smaller one, keep the remainder, and repeat with the smaller number and the remainder until the remainder becomes 0. The last non-zero remainder is the GCD. Because the remainders shrink quickly, even numbers with dozens of digits need only a few dozen divisions.
With more than two inputs the GCD is folded from left to right: gcd(a, b, c) = gcd(gcd(a, b), c). Each pairing gets its own block of divisions in the solution, so you can follow the whole chain.
How the calculator finds the LCM
For two numbers the LCM follows from the GCD: lcm(a, b) = |a × b| / gcd(a, b). For a longer list the LCM is folded in the same way, lcm(a, b, c) = lcm(lcm(a, b), c). As a cross-check the tool also factorizes each number (when all are at most 1015) and compares exponents: the GCD uses the smallest exponent of every prime and the LCM uses the largest. For 48 = 24 × 3 and 180 = 22 × 32 × 5 this gives gcd = 22 × 3 = 12 and lcm = 24 × 32 × 5 = 720.
Common mistakes
Multiplying all the numbers gives a common multiple, but usually not the least one. The identity gcd × lcm = product is true for exactly two numbers and false in general for three or more. Remember also that gcd(0, a) = |a|, that the LCM of a list containing 0 is defined as 0, and that negative numbers are handled through their absolute values.
Worked examples
These examples are computed by the same engine as the calculator above, so you can compare each step with your own working.
48 and 180
GCD (greatest common divisor)
12
LCM (least common multiple)
720
Step-by-step solution
Formula used
gcd(a, b) = gcd(b, a mod b) (Euclid), gcd(a, b, c) = gcd(gcd(a, b), c)
lcm(a, b) = |a × b| / gcd(a, b), lcm(a, b, c) = lcm(lcm(a, b), c)
Prime view: gcd takes the smallest exponent of each prime, lcm the largest.
NoteRead the numbers
Numbers: 48, 180
CalculateEuclid's algorithm: gcd(48, 180)
gcd(a, b) = gcd(b, a mod b); stop when the remainder is 0
180 = 3 × 48 + 36
48 = 1 × 36 + 12
36 = 3 × 12 + 0
The last non-zero remainder is 12, so gcd(48, 180) = 12.
CalculateLCM: lcm(48, 180)
lcm(a, b) = a × b / gcd(a, b)
gcd(48, 180) = 12
lcm = 48 × 180 / 12 = 8640 / 12 = 720
CalculateCross-check with prime factorization
gcd = product of p^min(exponents), lcm = product of p^max(exponents)
n1 = 48 = 2^4 × 3
n2 = 180 = 2^2 × 3^2 × 5
gcd = 2^2 × 3 = 12
lcm = 2^4 × 3^2 × 5 = 720
| Prime p | exponent in n1 | exponent in n2 | min | max |
|---|
| 2 | 4 | 2 | 2 | 4 |
| 3 | 1 | 2 | 1 | 2 |
| 5 | 0 | 1 | 0 | 1 |
CheckVerify the answer
48 / 12 = 4 (whole number, so 12 divides 48)
180 / 12 = 15 (whole number, so 12 divides 180)
720 / 48 = 15 (whole number, so 48 divides 720)
720 / 180 = 4 (whole number, so 180 divides 720)
gcd × lcm = 12 × 720 = 8640 = 48 × 180 = 8640
84, 126, 210
- Numbers:
(84); (126); (210)
GCD (greatest common divisor)
42
LCM (least common multiple)
1260
The identity gcd × lcm = product holds only for two numbers; for three or more it generally fails.
Step-by-step solution
Formula used
gcd(a, b) = gcd(b, a mod b) (Euclid), gcd(a, b, c) = gcd(gcd(a, b), c)
lcm(a, b) = |a × b| / gcd(a, b), lcm(a, b, c) = lcm(lcm(a, b), c)
Prime view: gcd takes the smallest exponent of each prime, lcm the largest.
NoteRead the numbers
Numbers: 84, 126, 210
CalculateEuclid's algorithm: gcd(84, 126)
gcd(a, b) = gcd(b, a mod b); stop when the remainder is 0
126 = 1 × 84 + 42
84 = 2 × 42 + 0
The last non-zero remainder is 42, so gcd(84, 126) = 42.
CalculateEuclid's algorithm: gcd(42, 210)
gcd(a, b) = gcd(b, a mod b); stop when the remainder is 0
210 = 5 × 42 + 0
The last non-zero remainder is 42, so gcd(42, 210) = 42.
CalculateLCM: lcm(84, 126)
lcm(a, b) = a × b / gcd(a, b)
gcd(84, 126) = 42
lcm = 84 × 126 / 42 = 10584 / 42 = 252
CalculateLCM: lcm(252, 210)
lcm(a, b) = a × b / gcd(a, b)
gcd(252, 210) = 42
lcm = 252 × 210 / 42 = 52920 / 42 = 1260
CalculateCross-check with prime factorization
gcd = product of p^min(exponents), lcm = product of p^max(exponents)
n1 = 84 = 2^2 × 3 × 7
n2 = 126 = 2 × 3^2 × 7
n3 = 210 = 2 × 3 × 5 × 7
gcd = 2 × 3 × 7 = 42
lcm = 2^2 × 3^2 × 5 × 7 = 1260
| Prime p | exponent in n1 | exponent in n2 | exponent in n3 | min | max |
|---|
| 2 | 2 | 1 | 1 | 1 | 2 |
| 3 | 1 | 2 | 1 | 1 | 2 |
| 5 | 0 | 0 | 1 | 0 | 1 |
| 7 | 1 | 1 | 1 | 1 | 1 |
CheckVerify the answer
84 / 42 = 2 (whole number, so 42 divides 84)
126 / 42 = 3 (whole number, so 42 divides 126)
210 / 42 = 5 (whole number, so 42 divides 210)
1260 / 84 = 15 (whole number, so 84 divides 1260)
1260 / 126 = 10 (whole number, so 126 divides 1260)
1260 / 210 = 6 (whole number, so 210 divides 1260)
1071 and 462
GCD (greatest common divisor)
21
LCM (least common multiple)
23562
Step-by-step solution
Formula used
gcd(a, b) = gcd(b, a mod b) (Euclid), gcd(a, b, c) = gcd(gcd(a, b), c)
lcm(a, b) = |a × b| / gcd(a, b), lcm(a, b, c) = lcm(lcm(a, b), c)
Prime view: gcd takes the smallest exponent of each prime, lcm the largest.
NoteRead the numbers
Numbers: 1071, 462
CalculateEuclid's algorithm: gcd(1071, 462)
gcd(a, b) = gcd(b, a mod b); stop when the remainder is 0
1071 = 2 × 462 + 147
462 = 3 × 147 + 21
147 = 7 × 21 + 0
The last non-zero remainder is 21, so gcd(1071, 462) = 21.
CalculateLCM: lcm(1071, 462)
lcm(a, b) = a × b / gcd(a, b)
gcd(1071, 462) = 21
lcm = 1071 × 462 / 21 = 494802 / 21 = 23562
CalculateCross-check with prime factorization
gcd = product of p^min(exponents), lcm = product of p^max(exponents)
n1 = 1071 = 3^2 × 7 × 17
n2 = 462 = 2 × 3 × 7 × 11
gcd = 3 × 7 = 21
lcm = 2 × 3^2 × 7 × 11 × 17 = 23562
| Prime p | exponent in n1 | exponent in n2 | min | max |
|---|
| 2 | 0 | 1 | 0 | 1 |
| 3 | 2 | 1 | 1 | 2 |
| 7 | 1 | 1 | 1 | 1 |
| 11 | 0 | 1 | 0 | 1 |
| 17 | 1 | 0 | 0 | 1 |
CheckVerify the answer
1071 / 21 = 51 (whole number, so 21 divides 1071)
462 / 21 = 22 (whole number, so 21 divides 462)
23562 / 1071 = 22 (whole number, so 1071 divides 23562)
23562 / 462 = 51 (whole number, so 462 divides 23562)
gcd × lcm = 21 × 23562 = 494802 = 1071 × 462 = 494802
Coprime: 35 and 64
GCD (greatest common divisor)
1
LCM (least common multiple)
2240
gcd = 1: the two numbers are coprime (relatively prime).
Step-by-step solution
Formula used
gcd(a, b) = gcd(b, a mod b) (Euclid), gcd(a, b, c) = gcd(gcd(a, b), c)
lcm(a, b) = |a × b| / gcd(a, b), lcm(a, b, c) = lcm(lcm(a, b), c)
Prime view: gcd takes the smallest exponent of each prime, lcm the largest.
NoteRead the numbers
Numbers: 35, 64
CalculateEuclid's algorithm: gcd(35, 64)
gcd(a, b) = gcd(b, a mod b); stop when the remainder is 0
64 = 1 × 35 + 29
35 = 1 × 29 + 6
29 = 4 × 6 + 5
6 = 1 × 5 + 1
5 = 5 × 1 + 0
The last non-zero remainder is 1, so gcd(35, 64) = 1.
CalculateLCM: lcm(35, 64)
lcm(a, b) = a × b / gcd(a, b)
gcd(35, 64) = 1
lcm = 35 × 64 / 1 = 2240 / 1 = 2240
CalculateCross-check with prime factorization
gcd = product of p^min(exponents), lcm = product of p^max(exponents)
n1 = 35 = 5 × 7
n2 = 64 = 2^6
gcd = 1 = 1
lcm = 2^6 × 5 × 7 = 2240
| Prime p | exponent in n1 | exponent in n2 | min | max |
|---|
| 2 | 0 | 6 | 0 | 6 |
| 5 | 1 | 0 | 0 | 1 |
| 7 | 1 | 0 | 0 | 1 |
CheckVerify the answer
35 / 1 = 35 (whole number, so 1 divides 35)
64 / 1 = 64 (whole number, so 1 divides 64)
2240 / 35 = 64 (whole number, so 35 divides 2240)
2240 / 64 = 35 (whole number, so 64 divides 2240)
gcd × lcm = 1 × 2240 = 2240 = 35 × 64 = 2240
Frequently asked questions
What is the GCD of two coprime numbers?
It is 1. Two numbers are coprime exactly when their only common positive divisor is 1, and then their LCM equals their product. For example gcd(35, 64) = 1 and lcm(35, 64) = 2240.
Can I enter zero or negative numbers?
Yes. Negative numbers are replaced by their absolute values. Zeros are ignored for the GCD because gcd(0, a) = |a|, and the LCM is reported as 0 whenever a zero is present. At least one number must be non-zero.
Why does gcd × lcm = product fail for three numbers?
The identity comes from counting each prime exponent once as a minimum and once as a maximum, which pairs up exactly for two numbers. For 4, 6 and 10 we get gcd = 2 and lcm = 60, so gcd × lcm = 120, but the product is 240.
How big can the numbers be?
Each number may have up to 40 digits. Euclid's algorithm is exact for any size; the prime-factorization cross-check is added only when all numbers are at most 1015.