LCM vs HCF (GCF): Difference, Formula, Examples
LCM vs HCF: the HCF (highest common factor, called GCF in the US) is the largest number that divides into all the given numbers. The LCM (least common multiple) is the smallest number that all the given numbers divide into. For 12 and 18: HCF = 6, LCM = 36.
LCM vs HCF: definitions side by side
HCF / GCF / GCD
Largest shared divisor. HCF ≤ the smallest number. Found from the shared primes at their lowest powers. 12 = 2² × 3, 18 = 2 × 3² → HCF = 2 × 3 = 6.
LCM
Smallest shared multiple. LCM ≥ the largest number. Found from every prime at its highest power. 12 = 2² × 3, 18 = 2 × 3² → LCM = 2² × 3² = 36.
Order of size for any two numbers a ≤ b: HCF ≤ a ≤ b ≤ LCM. The names differ by country: GCF (United States), HCF (United Kingdom, India), GCD (mathematics and programming).
The formula: LCM × HCF = a × b
For two numbers, LCM(a, b) × HCF(a, b) = a × b.
For 12 and 18: 36 × 6 = 216 = 12 × 18. The formula gives either value from the other: LCM = a × b ÷ HCF, and HCF = a × b ÷ LCM. The rule holds for two numbers only; for three or more numbers the product of the LCM and HCF is not the product of the numbers.
Worked example: HCF and LCM of 12 and 18
Prime factorization: LCM(12, 18)
Break each number into prime factors.
- 12 = 2 × 2 × 3 = 2² × 3
- 18 = 2 × 3 × 3 = 2 × 3²
Take the highest power of every prime that appears, then multiply them together.
| Prime | Highest power | From |
|---|---|---|
| 2 | 2² | 12 |
| 3 | 3² | 18 |
LCM = 2² × 3² = 36
LCM(12, 18) = 36
The HCF takes the same primes at their lowest powers: 2¹ × 3¹ = 6. Check: 36 × 6 = 216 = 12 × 18.
HCF and LCM of common pairs
| Numbers | HCF (GCF) | LCM | HCF × LCM | a × b |
|---|---|---|---|---|
| 4 and 8 | 4 | 8 | 32 | 32 |
| 12 and 18 | 6 | 36 | 216 | 216 |
| 24 and 36 | 12 | 72 | 864 | 864 |
| 16 and 50 | 2 | 400 | 800 | 800 |
| 25 and 50 | 25 | 50 | 1,250 | 1,250 |
| 2 and 4 | 2 | 4 | 8 | 8 |
When to use the HCF and when to use the LCM
| Question | Use | Example |
|---|---|---|
| Split into the largest equal groups | HCF | 12 red and 18 blue pens into identical packs: HCF 6 packs |
| Simplify a fraction | HCF | 12/18 ÷ 6 = 2/3 |
| When do repeating events coincide | LCM | Buses every 12 and 18 minutes meet after 36 minutes |
| Add or subtract fractions | LCM (as the LCD) | 1/12 + 1/18 uses denominator 36 |
A quick test: if the answer must be smaller than the numbers, the question wants the HCF; if the answer must be larger, the question wants the LCM.
How to find the HCF: the Euclidean algorithm
Divide the larger number by the smaller and keep the remainder. Divide the previous divisor by that remainder. Repeat until the remainder is 0; the last divisor is the HCF. For 36 and 24:
- 36 = 1 × 24 + 12
- 24 = 2 × 12 + 0
HCF(36, 24) = 12, and LCM = 36 × 24 ÷ 12 = 72. The GCF/Euclidean method for LCM is one of the four standard methods.
Venn diagram method for HCF and LCM
Put the prime factorisation of each number in a circle, with shared primes in the overlap. The overlap multiplied together is the HCF; every prime in the diagram multiplied together is the LCM.
Venn diagram: LCM(12, 18)
Put each number's prime factors in its circle. Factors shared by two (or three) numbers go where the circles overlap, written once. Multiply every factor in the diagram to get the LCM; the overlap alone gives the GCF.
LCM = 2 × 2 × 3 × 3 = 36
GCF = 2 × 3 = 6
LCM(12, 18) = 36
Coprime numbers
Two numbers with HCF = 1 are called coprime. Their LCM is their product: LCM(8, 9) = 72 and HCF(8, 9) = 1. Every pair page in the calculator, such as LCM of 6 and 8, states the HCF beside the LCM.
LCM and HCF in code
Every language uses the same two lines: the Euclidean algorithm for the GCD, then LCM = a ÷ GCD × b. Dividing before multiplying keeps the numbers small.
# Python (3.9+ also has math.gcd and math.lcm)
def gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
return a // gcd(a, b) * b// Java
static long gcd(long a, long b) { while (b != 0) { long t = a % b; a = b; b = t; } return a; }
static long lcm(long a, long b) { return a / gcd(a, b) * b; }/* C */
long gcd(long a, long b) { while (b) { long t = a % b; a = b; b = t; } return a; }
long lcm(long a, long b) { return a / gcd(a, b) * b; }For three or more numbers, fold the two-number function across the list: lcm(lcm(a, b), c).
Practice: HCF and LCM questions
Find the HCF and LCM of: (1) 16 and 50, (2) 25 and 50, (3) 2 and 4. Answers from the table above: (1) HCF 2, LCM 400; (2) HCF 25, LCM 50; (3) HCF 2, LCM 4. Enter any pair in the LCM calculator to see the working.
Frequently asked questions
What is the difference between HCF and LCM?
The HCF (highest common factor, also GCF) is the largest number that divides both numbers exactly. The LCM (least common multiple) is the smallest number both numbers divide into. For 12 and 18, HCF = 6 and LCM = 36.
Are GCF and HCF the same thing?
Yes. GCF (greatest common factor) is the US name, HCF (highest common factor) is the UK and Indian name, and GCD (greatest common divisor) is the name used in mathematics and programming. All three mean the same number.
What is the HCF and LCM formula?
For two numbers, LCM × HCF = a × b. So LCM = a × b ÷ HCF and HCF = a × b ÷ LCM. For 12 and 18: 36 × 6 = 216 = 12 × 18. The formula does not extend directly to three or more numbers.
How do you know when to use GCF or LCM?
Use the GCF to split things into the largest equal groups or to simplify a fraction. Use the LCM to find when repeating events coincide or to add fractions with different denominators.
What is the HCF of 12 and 18?
The HCF of 12 and 18 is 6. 12 = 2² × 3 and 18 = 2 × 3²; the shared primes at their lowest powers are 2 × 3 = 6.
What is the HCF of 24 and 36?
The HCF of 24 and 36 is 12, and the LCM is 72. Check: 12 × 72 = 864 = 24 × 36.
What is the HCF and LCM of 4 and 8?
The HCF of 4 and 8 is 4 and the LCM is 8. When one number divides the other, the smaller number is the HCF and the larger is the LCM.
How do I explain GCF and LCM to kids?
GCF: the biggest number that fits into both numbers, like the biggest box size that packs 12 and 18 exactly. LCM: the first number both counts reach, like counting in 4s and 6s and meeting at 12.
What is the difference between LCD and GCF?
The LCD (lowest common denominator) is the LCM of the denominators of fractions, used to add or subtract them. The GCF is used to simplify a single fraction. To add 1/4 and 1/6 use the LCD 12; to simplify 6/8 divide by the GCF 2.
How do I find the lowest common factor?
There is no "lowest common factor" in normal use: the lowest factor shared by any two numbers is always 1. The phrase usually means either the HCF (highest common factor) or the LCM (least common multiple). Decide which by the question: largest number that divides both → HCF; smallest number both divide into → LCM.
How do I find the LCM in Python, Java or C?
Compute the GCD with the Euclidean algorithm, then LCM = a / gcd(a, b) * b. Python: math.lcm(a, b) exists from version 3.9. Java and C have no built-in, so write a gcd loop and divide first to avoid overflow.
What is the easiest way to find the HCF?
The Euclidean algorithm: divide the larger number by the smaller, then divide the smaller by the remainder, and repeat until the remainder is 0. The last non-zero remainder is the HCF. For 36 and 24: 36 = 1 × 24 + 12, 24 = 2 × 12 + 0, so HCF = 12.
Sources
- Wikipedia: Least common multiple: definition, notation, LCM × GCD = a × b
- Wolfram MathWorld: Least Common Multiple: formal properties
- Common Core 6.NS.B.4: GCF and LCM in grade 6