LCM & HCF (GCD) Calculator
HCF and LCM with the working shown three ways — prime factors, ladder and Euclid.
HCF and LCM
This is the last answer worked out. Fix the input above to update it.
Highest common factor
Least common multiple
Method 1 · Prime factorization
Write each number as a product of primes. The HCF takes each prime to its smallest power; the LCM takes each prime to its largest power.
Method 2 · Division (ladder)
HCF ladder
Divide every number by a prime that divides all of them, until no prime does.
LCM ladder
Divide by the smallest prime that divides at least one number; bring the others down unchanged. Stop when every number is 1.
Method 3 · Euclid’s algorithm
Divide the larger number by the smaller and keep the remainder; repeat with the smaller number and the remainder. The last non-zero remainder is the HCF. For more than two numbers, find the HCF of the first two, then of that answer and the next number, and so on.
LCM from the HCF
Extended Euclid · Bézout coefficients
| Quotient q | Remainder r | s | t |
|---|
Check · HCF × LCM = product
Working
About the LCM & HCF (GCD) Calculator
Type two to twenty whole numbers — or fractions — to get their HCF (highest common factor, also called the GCD or GCF) and their LCM (least common multiple). The working is shown the three ways it is taught: prime factorization (smallest and largest powers of each prime), the division ladder, and Euclid’s algorithm, which also gives the LCM through LCM = a × b ÷ HCF.
For the curious there is more: the extended Euclidean algorithm with its full table and the Bézout coefficients (whole numbers x and y with a·x + b·y = HCF — for any number of inputs), the HCF × LCM = product check for two numbers, and the HCF and LCM of fractions. Numbers can have hundreds of digits; everything is computed exactly in your browser.
How to use it
- Choose Whole numbers or Fractions, then type the numbers separated by commas or spaces — for example
12, 18, 30, or1/2, 3/4, 5/6. - Read the HCF and LCM at the top. Notes say when the numbers are co-prime, or what a zero or a minus sign changes.
- Open the methods: prime factorization, the HCF and LCM division ladders, and Euclid’s algorithm step by step.
- For two numbers, see the extended Euclid table and the HCF × LCM check. Copy the answer with the Copy button.
Examples
12, 18, 30
HCF = 6, LCM = 180
12 = 2² × 3, 18 = 2 × 3², 30 = 2 × 3 × 5: HCF = 2 × 3, LCM = 2² × 3² × 5.
1071, 462
HCF = 21
1071 = 2 × 462 + 147; 462 = 3 × 147 + 21; 147 = 7 × 21 + 0.
240, 46
240 × (−9) + 46 × 47 = 2
20, 25, 30
LCM = 2 × 2 × 3 × 5 × 5 = 300
6, 10, 15
HCF = 1, LCM = 30
No number divides all three, but each pair shares a factor.
1/2, 3/4, 5/6
HCF = 1/12, LCM = 15/2
Common uses
- Homework on HCF and LCM by prime factorization, the division method and Euclid’s algorithm.
- Adding fractions with different denominators (the lowest common denominator is the LCM) or simplifying a fraction (divide by the HCF).
- Timing problems: two buses every 12 and 18 minutes leave together again after LCM(12, 18) = 36 minutes.
- Number theory and programming: gcd, modular inverses and Bézout coefficients for large numbers.
Three ways to find the HCF and LCM
- Prime factorization: write each number as a product of primes. The HCF is the product of the primes they all share, each to its smallest power; the LCM is the product of every prime that appears, each to its largest power.
- Division (ladder) method: for the HCF, divide all the numbers by a prime that divides every one of them, again and again; the HCF is the product of those primes. For the LCM, divide by the smallest prime that divides at least one number, bringing the others down unchanged, until every number is 1; the LCM is the product of all the divisors.
- Euclid’s algorithm: HCF(a, b) = HCF(b, a mod b), repeated until the remainder is 0 (Knuth, The Art of Computer Programming, Vol. 2, §4.5.2). It needs no factorization, so it is fast even for numbers with hundreds of digits. Then LCM(a, b) = a × b ÷ HCF(a, b). For more than two numbers, both are worked out one number at a time.
Bézout’s identity and the extended Euclidean algorithm
For any whole numbers a and b there are whole numbers x and y with a·x + b·y = HCF(a, b) — for example 240 × (−9) + 46 × 47 = 2. The extended Euclidean algorithm finds them by tracking, at every step, how each remainder is built from a and b. Once one solution is known, every other one is x + k·(b ÷ HCF) and y − k·(a ÷ HCF). The same idea works for more numbers, and it is how modular inverses are computed in cryptography.
HCF and LCM of fractions
Write each fraction in lowest terms first. Then:
- HCF of fractions = HCF of the numerators ÷ LCM of the denominators;
- LCM of fractions = LCM of the numerators ÷ HCF of the denominators.
So for 1/2, 3/4 and 5/6: HCF = HCF(1, 3, 5) ÷ LCM(2, 4, 6) = 1/12, and LCM = LCM(1, 3, 5) ÷ HCF(2, 4, 6) = 15/2. Each fraction divides 15/2 a whole number of times (15, 10 and 9), and 1/12 divides each fraction a whole number of times.
Why HCF × LCM = product works only for two numbers
For two numbers, each prime appears in the HCF with the smaller and in the LCM with the larger of its two powers, so HCF × LCM uses exactly the powers in a × b: 6 × 36 = 216 = 12 × 18. With three or more numbers the middle powers are left out, so the rule fails: for 12, 18 and 30, HCF × LCM = 6 × 180 = 1,080, but the product is 6,480.
Limitations
- Up to 20 numbers with up to 500 digits each. The prime-factorization and ladder methods are shown when every number can be broken into primes in well under a second; Euclid’s algorithm is shown for any size.
- Minus signs are ignored (the HCF and LCM are given as positive numbers). By convention HCF(0, n) = n and an LCM that involves 0 is 0.
- Long step lists are cut after 60 steps and ladders after 200 rows; the HCF and LCM themselves are always complete.
Privacy
Everything happens in your browser. What you enter or open here is not uploaded or stored by MySmartCoPilot.
Frequently asked questions
What is the HCF and LCM of 12 and 18?
HCF = 6 and LCM = 36. 12 = 2² × 3 and 18 = 2 × 3², so the HCF is 2 × 3 = 6 and the LCM is 2² × 3² = 36. Check: 6 × 36 = 216 = 12 × 18.
Are HCF, GCD and GCF the same thing?
Yes. Highest common factor (HCF), greatest common divisor (GCD) and greatest common factor (GCF) are three names for the largest number that divides all the numbers exactly.
How do I find the LCM by the division method?
Write the numbers in a row. Divide by the smallest prime that divides at least one of them, writing the quotients below and bringing down any number it does not divide. Repeat until the row is all 1s. The LCM is the product of the primes you divided by — for 20, 25 and 30: 2 × 2 × 3 × 5 × 5 = 300.
What does co-prime mean?
Numbers are co-prime (relatively prime) when their HCF is 1, like 8 and 15. Two co-prime numbers have their product as LCM. For three or more numbers, “pairwise co-prime” means every pair is co-prime — 6, 10 and 15 have HCF 1 but are not pairwise co-prime.
How is the LCM related to the HCF?
For two numbers, LCM = a × b ÷ HCF. That is the fastest way to get the LCM of big numbers: find the HCF with Euclid’s algorithm, then divide the product by it.
How do I find the HCF and LCM of fractions?
Reduce each fraction to lowest terms. The HCF is the HCF of the numerators over the LCM of the denominators; the LCM is the LCM of the numerators over the HCF of the denominators. Choose Fractions and the tool shows each step.
What are Bézout coefficients used for?
They show the HCF as a combination of the numbers, a·x + b·y = HCF. When the HCF is 1, x is the inverse of a modulo b — the step used in RSA cryptography and in solving equations such as 7x ≡ 1 (mod 26).