12, 18 and 30
- Whole numbers
- 12, 18, 30
- Greatest common divisor
- 6
- Least common multiple
- 180
Checked against: Independent calculation
GCD and LCM calculator
Greatest common divisor (GCD, GCF or HCF) and least common multiple (LCM) of two or more whole numbers, with Euclid's algorithm step by step.
By AdminDrafted with AI writing toolsUpdated Checked examples: 6
Greatest common divisor
Greatest common divisor: 6
- Least common multiple
- 180
The largest number dividing 12, 18 and 30 exactly is 6; the smallest positive number they all divide into is 180.
Euclid's algorithm as squares: 12 × 18 rectangle
Euclid's algorithm, a = q·b + r
| Pair | a | b | Quotient q | Remainder r |
|---|---|---|---|---|
| gcd(12, 18) | 18 | 12 | 1 | 6 |
| gcd(12, 18) | 12 | 6 | 2 | 0 |
| gcd(6, 30) | 30 | 6 | 5 | 0 |
How it's calculated S
Euclid's algorithm for gcd(12, 18)
Divide, keep the remainder, repeat with the divisor; the last non-zero remainder is the gcd.
Least common multiple with 18
Euclid's algorithm for gcd(6, 30)
Divide, keep the remainder, repeat with the divisor; the last non-zero remainder is the gcd.
Least common multiple with 30
About the GCD and LCM calculator
The greatest common divisor (GCD, also called the greatest common factor or highest common factor) is the largest whole number that divides every input; the least common multiple (LCM) is the smallest positive number that every input divides. Euclid's algorithm finds the GCD by repeatedly replacing the larger number with its remainder after division by the smaller: gcd(1071, 462) = gcd(462, 147) = gcd(147, 21) = 21. The LCM follows from lcm(a, b) = |a × b| ÷ gcd(a, b), applied a pair at a time.
Reducing fractions uses the GCD; adding fractions and lining up repeating schedules use the LCM. For the default 12, 18 and 30 the GCD is 6 and the LCM is 180, so events every 12, 18 and 30 days next coincide after 180 days.
For two numbers the calculator also gives the Bézout identity from the extended Euclidean algorithm: 21 = 1071 × (−3) + 462 × 7. Negative inputs count by their absolute value, gcd(0, n) = n, and a list containing 0 has an LCM of 0.
How to find the GCF and LCM
The greatest common factor (GCF) is the largest number that divides every input; the least common multiple (LCM) is the smallest positive number that every input divides. For 6 and 8 the GCF is 2 and the LCM is 24. For two numbers, LCM = a × b ÷ GCF: 48 ÷ 2 = 24.
The GCF is also called the greatest common divisor (GCD) or the highest common factor (HCF). All three names mean the same number.
LCM of common pairs
For small numbers, list multiples of the larger number until the smaller one divides one of them. For 15 and 20, the multiples of 20 are 20, 40 and 60, and 60 is the first that 15 divides. The same method gives:
- LCM of 4 and 6: 12
- LCM of 6 and 8: 24
- LCM of 8 and 12: 24
- LCM of 10 and 15: 30
- LCM of 15 and 20: 60
Larger numbers: prime factors or Euclid's algorithm
Write each number as a product of primes. The GCF takes the lower power of each prime the numbers share, and the LCM takes the higher power of every prime that appears.
For 20 = 2² × 5 and 25 = 5², the only shared prime is 5, so the HCF of 20 and 25 is 5. The LCM is 2² × 5² = 100. The prime factorization calculator gives these decompositions for larger numbers.
Euclid's method avoids factoring. Divide the larger number by the smaller, keep the remainder, and repeat with the previous divisor and that remainder. The last nonzero remainder is the GCF.
For 105 and 120: 120 = 1 × 105 + 15, then 105 = 7 × 15 + 0, so the GCF is 15. The LCM follows from the product rule: 105 × 120 ÷ 15 = 840.
Run backwards, Euclid's steps also give Bézout's identity: integers x and y with ax + by = gcd(a, b). For 240 and 46, 2 = 240 × (−9) + 46 × 47, since −2,160 + 2,162 = 2. The coefficients can be negative and are not unique.
Worked GCF and LCM examples
Each row lists the inputs together; for three numbers, both results apply to the whole list.
| Whole numbers | GCF / GCD | LCM |
|---|---|---|
| 12, 18, 30 | 6 | 180 |
| 1071, 462 | 21 | 23562 |
| 240, 46 | 2 | 5520 |
| 17, 31 | 1 | 527 |
| 0, 5 | 5 | 0 |
| -12, 18 | 6 | 36 |
| 8, 12 | 4 | 24 |
| 7, 14, 21 | 7 | 42 |
| 1, 100 | 1 | 100 |
| 0, -24, 36 | 12 | 0 |
| 6, 6 | 6 | 6 |
| 99991, 99989 | 1 | 9998000099 |
Numbers with a GCF of 1 are coprime, and their LCM is simply their product: 17 × 31 = 527. Coprime numbers need not be prime; 8 and 9 are both composite and share no factor.
Signs do not affect divisibility, so −12 and 18 have GCF 6 and LCM 36. A zero next to a nonzero number gives gcd(0, 5) = 5 and an LCM of 0. A list of only zeros has no GCF, because every positive integer divides 0.
Three or more numbers
Work through the list a pair at a time. For 130, 520 and 845, gcd(130, 520) = 130. Then 845 = 6 × 130 + 65 and 130 = 2 × 65 + 0, so gcd(130, 845) = 65, the GCF of all three.
The LCM works the same way, pair by pair. The product shortcut does not extend: for 12, 18 and 30, the product 6,480 divided by the GCF 6 gives 1,080, but the LCM is 180.
Where the GCF and LCM are used
- Simplifying fractions: dividing top and bottom by the GCF gives lowest terms, so 18/24 = 3/4 after dividing by 6.
- Adding fractions: the least common denominator is the LCM of the denominators. For 5/12 + 7/18 it is 36; the fraction calculator finishes the sum.
- Repeating schedules: buses leaving every 12 and 18 minutes leave together again after lcm(12, 18) = 36 minutes.
Entering the numbers
- Separate numbers with commas, spaces or line breaks, so 1,000 must be typed as 1000.
- Enter 2 to 100 whole numbers. Negative numbers count by their absolute value.
To list every divisor of a single number instead, use the factor calculator.
Worked examples
Euclid's 1071 and 462
- Whole numbers
- 1071, 462
- Greatest common divisor
- 21
- Least common multiple
- 23,562
- Bézout identity
- 21 = 1071·(−3) + 462·7
Checked against: Wikipedia — Euclidean algorithm worked example (gcd 21)
Extended Euclid on 240 and 46
- Whole numbers
- 240 46
- Greatest common divisor
- 2
- Least common multiple
- 5,520
- Bézout identity
- 2 = 240·(−9) + 46·47
Checked against: Wikipedia — Extended Euclidean algorithm example table (s = −9, t = 47)
Coprime 17 and 31
- Whole numbers
- 17, 31
- Greatest common divisor
- 1
- Least common multiple
- 527
Checked against: Both prime, so gcd 1 and lcm 17 × 31 = 527
Questions
How do you find the GCD of two numbers?
Use Euclid's algorithm: divide the larger number by the smaller, keep the remainder, and repeat with the divisor and the remainder until the remainder is 0; the last non-zero remainder is the GCD. For 1071 and 462: 1071 = 2 × 462 + 147, 462 = 3 × 147 + 21, 147 = 7 × 21 + 0, so the GCD is 21. By Lamé's theorem it never needs more than five steps per digit of the smaller number.
How do you find the LCM of two numbers?
Divide their product by their GCD: lcm(a, b) = a × b ÷ gcd(a, b). For 12 and 18, gcd = 6, so lcm = 216 ÷ 6 = 36. For more numbers, go one pair at a time: lcm(36, 30) = 1,080 ÷ 6 = 180, so the LCM of 12, 18 and 30 is 180. Listing multiples (12, 24, 36 …) reaches the same answer, but slowly for large numbers.
What is the difference between GCD, GCF and HCF?
There is none: greatest common divisor (GCD), greatest common factor (GCF) and highest common factor (HCF) are three names for the same number. GCF and HCF are the usual school terms, GCF mostly in the US and HCF in the UK and India, while GCD is the name in number theory and programming, as in Python's math.gcd. Under every name, gcd(12, 18) = 6.
How are the GCD and LCM related?
For two positive whole numbers, gcd(a, b) × lcm(a, b) = a × b; with 12 and 18, 6 × 36 = 216 = 12 × 18. In prime factors, the GCD takes the lower power of each shared prime and the LCM the higher power of every prime: 12 = 2² × 3 and 18 = 2 × 3², so the GCD is 2 × 3 = 6 and the LCM is 2² × 3² = 36. The product rule does not extend to three or more numbers.
What does it mean when two numbers are coprime?
Their GCD is 1, so they share no prime factor, and their LCM is simply their product. 17 and 31 are coprime, with an LCM of 17 × 31 = 527, and so are 8 and 15 although neither is prime. A fraction is in lowest terms exactly when its numerator and denominator are coprime.
About this calculator
Sources
- Euclid, Elements, Book VII, Propositions 1–2
- Knuth, The Art of Computer Programming Vol. 2, §4.5.2 (Euclid's algorithm)
- Wikipedia — Extended Euclidean algorithm (worked example 240, 46)
Checked against references
This calculator includes 6 worked examples with independently sourced answers. They run in the test suite, and you can run them here too.