Chapter 1 · Real Numbers

1.2 HCF and LCM by Prime Factorisation

Line up the prime factorisations: the HCF takes the smallest power of each common prime, the LCM the greatest power of every prime, and for two numbers $\operatorname{HCF}\times\operatorname{LCM}$ equals their product.

A sweet shop has $252$ laddoos and $396$ barfis and wants to pack them into identical boxes, as many boxes as possible, with nothing left over. Three garden sprinklers switch on every $12$, $18$ and $30$ minutes; when will they all come on together again? The first question asks for the highest common factor of some numbers; the second asks for their lowest common multiple.

You have found HCF and LCM before by listing factors and multiples. That works for small numbers but quickly becomes slow. In this section the prime factorisations from Section 1.1 do the work for us. Once you have written each number as a product of primes, the HCF and LCM can be read off almost at once. We also meet a neat link between them: for any two numbers, $\operatorname{HCF}\times\operatorname{LCM}$ is the product of the numbers.

HCF and LCM from prime factorisations

📘 Definition 1.3 — HCF and LCM
Let $a$ and $b$ be natural numbers.
The highest common factor $\operatorname{HCF}(a,b)$ is the largest natural number that divides both $a$ and $b$.
The lowest common multiple $\operatorname{LCM}(a,b)$ is the smallest natural number that is a multiple of both $a$ and $b$.
Two numbers whose HCF is $1$ are called co-prime (for example $8$ and $15$). The same definitions apply to three or more numbers.

Why do prime factorisations help? A factor of $a$ can only use the primes of $a$, with exponents no bigger than in $a$ (Exercise III.8 of Section 1.1). So a common factor can use only primes that are in both numbers, each with an exponent no bigger than in either number. The largest common factor takes as much as it is allowed: the smaller of the two exponents. A common multiple must contain everything in $a$ and everything in $b$, so the smallest one takes each prime with the larger exponent.

📐 Theorem 1.2 — HCF and LCM by prime factorisation
Write the natural numbers as products of primes. Then
  • $\operatorname{HCF}$ $=$ the product of the smallest power of each prime that is common to all the numbers (if no prime is common, the HCF is $1$);
  • $\operatorname{LCM}$ $=$ the product of the greatest power of each prime that appears in any of the numbers.
✏️ Example 1 — HCF and LCM of two numbers
Find $\operatorname{HCF}(84,120)$ and $\operatorname{LCM}(84,120)$ by prime factorisation.
Factorise $84=2^2\times3\times7$ and $120=2^3\times3\times5$.
HCF Common primes: $2$ and $3$. Smallest powers: $2^2$ (from $84$) and $3^1$. So $\operatorname{HCF}=2^2\times3=12$.
LCM All primes: $2, 3, 5, 7$. Greatest powers: $2^3$, $3^1$, $5^1$, $7^1$. So $\operatorname{LCM}=2^3\times3\times5\times7=840$.
Check $84\div12=7$ and $120\div12=10$ (whole numbers, and $7$, $10$ share no factor); $840\div84=10$ and $840\div120=7$. ✓
✏️ Example 2 — Reading powers carefully
Find the HCF and LCM of $360$ and $756$.
Factorise $360=2^3\times3^2\times5$ and $756=4\times189=2^2\times3^3\times7$.
Line them up $$\begin{array}{c|cccc}&2&3&5&7\\\hline 360&3&2&1&0\\756&2&3&0&1\\\hline\text{HCF (smaller)}&2&2&0&0\\\text{LCM (greater)}&3&3&1&1\end{array}$$ (The table shows exponents; an exponent $0$ means the prime is absent.)
Answer $\operatorname{HCF}=2^2\times3^2=36$ and $\operatorname{LCM}=2^3\times3^3\times5\times7=7560$.
Check $360\div36=10$, $756\div36=21$; $7560\div360=21$, $7560\div756=10$. ✓
Interactive 1 — Prime Bags: HCF in the Middle, LCM Everywhere

The prime factors of $a$ (blue) and $b$ (red) fly into a Venn diagram. A prime that the two numbers share lands in the middle, once for each copy they have in common. The middle multiplies to the HCF; everything inside the two circles multiplies to the LCM. Press Play to see several pairs, or set $a$ and $b$ yourself.

84120
HCF (middle)—
LCM (whole diagram)—
HCF × LCM—
$a\times b$—

HCF × LCM = product of the two numbers

In Example 1, $\operatorname{HCF}\times\operatorname{LCM}=12\times840=10080$ and $84\times120=10080$. In Example 2, $36\times7560=272160=360\times756$. This is no accident. Look at a single prime: if it appears as $p^m$ in $a$ and $p^n$ in $b$, then the HCF takes the smaller of $m, n$ and the LCM takes the larger. Smaller $+$ larger $=m+n$, which is exactly the exponent of $p$ in $a\times b$. This happens for every prime, so the two products are equal. In Interactive 1 you can see it: the middle tokens are counted once in the HCF and once more in the LCM, just as they appear once in $a$ and once in $b$.

📐 Theorem 1.3 — HCF × LCM for two numbers
For any two natural numbers $a$ and $b$, $$\operatorname{HCF}(a,b)\times\operatorname{LCM}(a,b)=a\times b .$$
⚠️ Only for two numbers

The rule is about two numbers. For three numbers it usually fails. Take $6, 10, 15$: $\operatorname{HCF}=1$ and $\operatorname{LCM}=30$, so $\operatorname{HCF}\times\operatorname{LCM}=30$, but $6\times10\times15=900$. For three numbers, always find the HCF and LCM directly from the prime factorisations.

Two quick tests catch many errors: the HCF must divide the LCM, and the HCF can be no bigger than the smaller number while the LCM can be no smaller than the larger number.

✏️ Example 3 — Finding the missing number
The HCF of two numbers is $18$ and their LCM is $1260$. One of the numbers is $126$. Find the other.
Formula $\operatorname{HCF}\times\operatorname{LCM}=a\times b$, so $18\times1260=126\times b$.
Solve $b=\dfrac{18\times1260}{126}=\dfrac{22680}{126}=180$.
Check $126=2\times3^2\times7$ and $180=2^2\times3^2\times5$: HCF $=2\times3^2=18$ ✓ and LCM $=2^2\times3^2\times5\times7=1260$ ✓.

Three numbers, and word problems

Theorem 1.2 works for any number of numbers: list all the prime factorisations side by side. For the HCF use only primes common to all of them.

✏️ Example 4 — HCF and LCM of three numbers
Find the HCF and LCM of $18$, $30$ and $42$. Is $\operatorname{HCF}\times\operatorname{LCM}$ equal to $18\times30\times42$?
Factorise $18=2\times3^2$, $30=2\times3\times5$, $42=2\times3\times7$.
HCF Primes common to all three: $2$ and $3$, smallest powers $2^1$ and $3^1$. $\operatorname{HCF}=6$.
LCM Greatest powers of $2, 3, 5, 7$: $2^1, 3^2, 5^1, 7^1$. $\operatorname{LCM}=2\times9\times5\times7=630$.
Compare $6\times630=3780$, but $18\times30\times42=22680$. Not equal — the two-number rule does not extend to three numbers.
🧭 Problem-solving strategy — HCF or LCM?
  1. Ask: are we cutting or sharing the given amounts into equal parts as large as possible (or into as many identical groups as possible)? Then the answer must divide each amount: use the HCF.
  2. Or are we waiting for things that repeat (bells, lights, laps, buses) to happen together, or looking for the smallest amount that several numbers divide into? Then the answer is a common multiple: use the LCM.
  3. Put all quantities in the same unit first (metres to centimetres, hours to minutes).
  4. Check that your answer makes sense: an HCF answer is no bigger than the given numbers; an LCM answer is no smaller.
✏️ Example 5 — Sprinklers in a park (LCM)
Three sprinklers in a park in Pune switch on every $12$, $18$ and $30$ minutes. All three switch on together at 6:00 a.m. When will they next switch on together?
Which one? We wait for repeating events to coincide, so we need the LCM.
Factorise $12=2^2\times3$, $18=2\times3^2$, $30=2\times3\times5$.
LCM $2^2\times3^2\times5=180$ minutes $=3$ hours.
Answer They next switch on together at 9:00 a.m. Check: $180\div12=15$, $180\div18=10$, $180\div30=6$ — whole numbers. ✓
✏️ Example 6 — Packing sweets (HCF)
A sweet shop has $252$ laddoos and $396$ barfis. They are to be packed in identical boxes, each with the same number of laddoos and the same number of barfis, with none left over. What is the largest number of boxes possible, and what goes in each box?
Which one? The number of boxes must divide $252$ and $396$ exactly, and we want the largest such number: the HCF.
Factorise $252=2^2\times3^2\times7$ and $396=2^2\times3^2\times11$.
HCF $2^2\times3^2=36$.
Answer $36$ boxes, each with $252\div36=7$ laddoos and $396\div36=11$ barfis.
Interactive 2 — When Do the Lights Flash Together?

Each light flashes every $p$ seconds, starting together at $t=0$. Dots mark the flashes of each light; the thick purple lines mark the moments when all of them flash at once. The first purple line after $0$ is at the LCM of the periods. Press Play to run the clock and watch the lamps on the left.

4610
time $t$ (s)—
LCM of the periods—
flashes before first common one—

Exercises

I
Find the HCF and LCM of each pair by prime factorisation, and check that $\operatorname{HCF}\times\operatorname{LCM}$ equals the product of the two numbers.
  • 1 $24$ and $90$
  • 2 $56$ and $84$
  • 3 $72$ and $108$
  • 4 $135$ and $225$
  • 5 $210$ and $495$
  • 6 $17$ and $23$
  • 7 $252$ and $588$
  • 8 $1001$ and $1287$
Check: type two or three numbers and compare the HCF and LCM with yours
factorisations—
HCF—
LCM—
1 $24=2^3\times3$, $90=2\times3^2\times5$. HCF $=2\times3=6$, LCM $=2^3\times3^2\times5=360$. Check: $6\times360=2160=24\times90$. ✓
2 $56=2^3\times7$, $84=2^2\times3\times7$. HCF $=2^2\times7=28$, LCM $=2^3\times3\times7=168$. Check: $28\times168=4704=56\times84$. ✓
3 $72=2^3\times3^2$, $108=2^2\times3^3$. HCF $=2^2\times3^2=36$, LCM $=2^3\times3^3=216$. Check: $36\times216=7776=72\times108$. ✓
4 $135=3^3\times5$, $225=3^2\times5^2$. HCF $=3^2\times5=45$, LCM $=3^3\times5^2=675$. Check: $45\times675=30375=135\times225$. ✓
5 $210=2\times3\times5\times7$, $495=3^2\times5\times11$. HCF $=3\times5=15$, LCM $=2\times3^2\times5\times7\times11=6930$. Check: $15\times6930=103950=210\times495$. ✓
6 Both are prime, so they are co-prime: HCF $=1$, LCM $=17\times23=391$. Check: $1\times391=391$. ✓
7 $252=2^2\times3^2\times7$, $588=2^2\times3\times7^2$. HCF $=2^2\times3\times7=84$, LCM $=2^2\times3^2\times7^2=1764$. Check: $84\times1764=148176=252\times588$. ✓
8 $1001=7\times11\times13$, $1287=3^2\times11\times13$. HCF $=11\times13=143$, LCM $=3^2\times7\times11\times13=9009$. Check: $143\times9009=1288287=1001\times1287$. ✓
II
Three numbers. Find the HCF and LCM by prime factorisation.
  • 1 $8$, $12$, $20$
  • 2 $9$, $15$, $25$
  • 3 $24$, $36$, $60$
  • 4 $30$, $45$, $75$
  • 5 $14$, $35$, $49$
  • 6 $16$, $40$, $56$
  • 7 Show that for $4$, $6$ and $9$, $\operatorname{HCF}\times\operatorname{LCM}$ is not equal to the product of the three numbers.
1 $8=2^3$, $12=2^2\times3$, $20=2^2\times5$. HCF $=2^2=4$, LCM $=2^3\times3\times5=120$.
2 $9=3^2$, $15=3\times5$, $25=5^2$. No prime is common to all three, so HCF $=1$. LCM $=3^2\times5^2=225$.
3 $24=2^3\times3$, $36=2^2\times3^2$, $60=2^2\times3\times5$. HCF $=2^2\times3=12$, LCM $=2^3\times3^2\times5=360$.
4 $30=2\times3\times5$, $45=3^2\times5$, $75=3\times5^2$. HCF $=3\times5=15$, LCM $=2\times3^2\times5^2=450$.
5 $14=2\times7$, $35=5\times7$, $49=7^2$. HCF $=7$, LCM $=2\times5\times7^2=490$.
6 $16=2^4$, $40=2^3\times5$, $56=2^3\times7$. HCF $=2^3=8$, LCM $=2^4\times5\times7=560$.
7 $4=2^2$, $6=2\times3$, $9=3^2$: HCF $=1$, LCM $=2^2\times3^2=36$, so $\operatorname{HCF}\times\operatorname{LCM}=36$, while $4\times6\times9=216$. Not equal.
III
Using $\operatorname{HCF}\times\operatorname{LCM}=a\times b$.
  • 1 The HCF of two numbers is $9$ and their LCM is $540$. One number is $108$. Find the other.
  • 2 The product of two numbers is $1350$ and their HCF is $15$. Find their LCM, and find one possible pair of numbers.
  • 3 Can two numbers have HCF $16$ and LCM $380$? Give a reason.
  • 4 Two co-prime numbers have LCM $391$. One of them is $17$. Find the other.
  • 5 Challenge. Explain why $\operatorname{HCF}(n,n+1)=1$ for every natural number $n$, and hence write down $\operatorname{LCM}(n,n+1)$.
1 $b=\dfrac{9\times540}{108}=\dfrac{4860}{108}=45$. Check: $108=2^2\times3^3$, $45=3^2\times5$: HCF $=9$, LCM $=2^2\times3^3\times5=540$. ✓
2 $\operatorname{LCM}=\dfrac{1350}{15}=90$. Both numbers are multiples of $15$: write them as $15m$ and $15n$ with $m$, $n$ co-prime and $225mn=1350$, so $mn=6$. Pairs: $15$ and $90$, or $30$ and $45$.
3 No. The HCF always divides the LCM, but $380\div16=23.75$ is not a whole number.
4 For co-prime numbers HCF $=1$, so the LCM is the product: other number $=391\div17=23$.
5 A number that divides both $n$ and $n+1$ also divides their difference, $(n+1)-n=1$. The only natural number dividing $1$ is $1$, so the HCF is $1$. Then $\operatorname{LCM}=\dfrac{n(n+1)}{1}=n(n+1)$.
IV
Word problems. Decide first whether you need the HCF or the LCM.
  • 1 Two traffic lights at a crossing in Bengaluru change every $48$ seconds and every $72$ seconds. They change together at 9:00:00 a.m. When do they next change together?
  • 2 A courtyard measuring $4.2$ m by $3.6$ m is to be paved with identical square tiles, as large as possible, with no cutting. Find the side of each tile and the number of tiles.
  • 3 Three ribbons of lengths $84$ cm, $126$ cm and $210$ cm are cut into pieces of equal length, as long as possible, with nothing wasted. Find the length of each piece and the total number of pieces.
  • 4 On a sports day, Asha, Bilal and Chitra run round a track, taking $6$, $8$ and $10$ minutes per lap. They start together at the starting line. After how many minutes are they next together at the start, and how many laps has each run by then?
  • 5 Find the smallest number which leaves remainder $5$ when divided by each of $12$, $16$ and $24$.
  • 6 Find the greatest number which divides $245$ and $1029$ leaving remainder $5$ in each case.
  • 7 Find the smallest 4-digit number that is divisible by each of $12$, $15$ and $18$.
  • 8 Modelling. In the USA, periodical cicadas spend $13$ or $17$ years underground and then all emerge in the same summer. In 2024 a $13$-year brood and a $17$-year brood emerged together in Illinois. If both keep their cycles, in which year will they next emerge together? Why might prime cycle lengths help the insects?
1 LCM: $48=2^4\times3$, $72=2^3\times3^2$, LCM $=2^4\times3^2=144$ s $=2$ min $24$ s. Next together at 9:02:24 a.m.
2 HCF, in cm: $420=2^2\times3\times5\times7$, $360=2^3\times3^2\times5$, HCF $=2^2\times3\times5=60$ cm. Tiles: $(420\div60)\times(360\div60)=7\times6=42$ tiles of side $60$ cm.
3 HCF: $84=2^2\times3\times7$, $126=2\times3^2\times7$, $210=2\times3\times5\times7$, HCF $=2\times3\times7=42$ cm. Pieces: $2+3+5=10$.
4 LCM: $6=2\times3$, $8=2^3$, $10=2\times5$, LCM $=2^3\times3\times5=120$ minutes ($2$ hours). Laps: Asha $120\div6=20$, Bilal $120\div8=15$, Chitra $120\div10=12$.
5 $\operatorname{LCM}(12,16,24)$: $12=2^2\times3$, $16=2^4$, $24=2^3\times3$, LCM $=2^4\times3=48$. The number is $48+5=53$. Check: $53=4\times12+5=3\times16+5=2\times24+5$. ✓
6 The number divides $245-5=240$ and $1029-5=1024$ exactly. $240=2^4\times3\times5$, $1024=2^{10}$, HCF $=2^4=16$. Check: $245=15\times16+5$, $1029=64\times16+5$. ✓
7 $12=2^2\times3$, $15=3\times5$, $18=2\times3^2$, LCM $=2^2\times3^2\times5=180$. Multiples of $180$: $900$ (3 digits), $1080$. Answer: $1080$.
8 $13$ and $17$ are different primes, so $\operatorname{LCM}=13\times17=221$ years: next together in $2024+221=2245$. A predator with a short cycle (say $2$–$6$ years) can only line up with a prime cycle every $13\times(\text{its cycle})$ years or so, while a cycle such as $12$ would meet predators with cycles $2, 3, 4$ and $6$ every single time. (The Research–Teaching Nexus below explores this.)
🎯 Exam corner Board · 1 markBoard · 2 marksBoard · 3 marksBoard · Case study

How this is examined: expect short questions on HCF and LCM from given prime factorisations, the relation $\operatorname{HCF}\times\operatorname{LCM}=a\times b$, and 3-mark word problems where you must decide between HCF and LCM. Always write the prime factorisations — they carry marks even if you slip later.

E1. Board · 1 mark The HCF of two numbers is $12$ and their product is $2160$. Their LCM is  (A) $120$  (B) $180$  (C) $160$  (D) $25920$

Idea $\operatorname{LCM}=\dfrac{a\times b}{\operatorname{HCF}}=\dfrac{2160}{12}=180$. (For example $36$ and $60$ have HCF $12$ and LCM $180$.)
Trap (D) $=2160\times12$ comes from multiplying instead of dividing. (C) fails the quick test: $160$ is not a multiple of $12$, but the HCF must divide the LCM.
Answer (B) $180$.

E2. Board · 1 mark Assertion (A): For the numbers $6$, $10$ and $15$, $\operatorname{HCF}\times\operatorname{LCM}\ne6\times10\times15$. Reason (R): $\operatorname{HCF}\times\operatorname{LCM}=$ product of the numbers holds for any two natural numbers, but not in general for three.
(A) Both A and R are true and R is the correct explanation of A.  (B) Both A and R are true but R is not the correct explanation of A.  (C) A is true but R is false.  (D) A is false but R is true.

Check A HCF $=1$, LCM $=30$, so $1\times30=30\ne900$. True.
Check R True (Theorem 1.3 is about two numbers), and it explains why A can happen.
Answer (A). A student who believes the rule works for any number of numbers would wrongly choose (D).

E3. Board · 2 marks Find the HCF and LCM of $2^4\times3\times5^2$ and $2^2\times3^3\times5$.

HCF Smallest powers of the common primes $2, 3, 5$: $2^2\times3\times5=60$. (1 mark)
LCM Greatest powers: $2^4\times3^3\times5^2=16\times27\times25=10800$. (1 mark)
Check The numbers are $1200$ and $540$; $60\times10800=648000=1200\times540$. ✓

E4. Board · 3 marks Three alarms ring every $18$, $24$ and $40$ minutes. They ring together at 8:00 a.m. At what time will they next ring together?

Factorise $18=2\times3^2$, $24=2^3\times3$, $40=2^3\times5$. (1 mark)
LCM $2^3\times3^2\times5=360$ minutes $=6$ hours. (1 mark)
Answer They ring together again at 2:00 p.m. (1 mark)

E5. Board · 3 marks For a school sports day there are $156$ red and $204$ blue T-shirts. They are to be packed into identical kits, each with the same number of red and the same number of blue T-shirts, with none left over. Find the greatest number of kits and the contents of each kit.

Which one? The number of kits must divide both $156$ and $204$, and be as large as possible: HCF.
Factorise $156=2^2\times3\times13$, $204=2^2\times3\times17$, so HCF $=2^2\times3=12$.
Answer $12$ kits, each with $13$ red and $17$ blue T-shirts.

E6. Board · Case study Railway junction. At a busy junction, trains to Delhi leave every $15$ minutes, trains to Jaipur every $20$ minutes and trains to Agra every $36$ minutes. All three leave together at 5:30 a.m.
(i) After how many minutes do a Delhi train and a Jaipur train next leave together? (1 mark)
(ii) After how many minutes do all three next leave together? (1 mark)
(iii) How many times do all three leave together from 5:30 a.m. to 11:30 p.m. on the same day, both times included? (2 marks)

(i) $15=3\times5$, $20=2^2\times5$: $\operatorname{LCM}=2^2\times3\times5=60$ minutes.
(ii) $36=2^2\times3^2$: $\operatorname{LCM}(15,20,36)=2^2\times3^2\times5=180$ minutes $=3$ hours.
(iii) Together at 5:30, 8:30, 11:30 a.m., 2:30, 5:30, 8:30 and 11:30 p.m. From 5:30 a.m. to 11:30 p.m. is $18$ hours $=6$ gaps of $3$ hours, so $6+1=7$ times.
🔬 Research–Teaching NexusMini project · optional, about 45 minutes

Research question. Why do periodical cicadas have life cycles of $13$ and $17$ years — both prime numbers? Can the LCM explain it?

Why it matters. Biologists have suggested that a prime cycle helps cicadas avoid predators and parasites whose populations also rise and fall in cycles. If a predator peaks every $p$ years and the cicadas emerge every $c$ years, the two meet every $\operatorname{LCM}(c,p)$ years. The same LCM reasoning is used by timetable planners at Indian Railways and metro systems, and by engineers who make sure machine parts with different rotation periods do not keep hitting the same spot.

What to do.

  1. Make a table with cicada cycles $c=12, 13, 14, 15, 16, 17, 18$ (rows) and predator cycles $p=2, 3, 4, 5, 6$ (columns).
  2. In each cell write $\operatorname{LCM}(c,p)$, using prime factorisation. (In a spreadsheet, =LCM(A2,B1) checks your work.)
  3. Count, for each $c$, how many predator cycles meet the cicadas at every emergence, i.e. have $\operatorname{LCM}(c,p)=c$.
  4. Which values of $c$ do best? What do they have in common?
  5. Look up the 2024 "double brood" emergence in the USA and write one paragraph on what happened.

Tools: Notebook, or a spreadsheet with the LCM function

Hand in: Your completed $7\times5$ table, the count for each cycle length, and a short conclusion (4–5 sentences) on whether the LCM supports the "prime cycle" idea.

Going further. Find the timetable of two bus or metro routes from the same stop near you. If buses leave every $p$ and $q$ minutes, how often do they leave together? Does the real timetable agree?

Teacher/parent note: the number of predator cycles (out of $2$–$6$) with $\operatorname{LCM}(c,p)=c$ is $4$ for $c=12$, $0$ for $13$, $1$ for $14$, $2$ for $15$, $2$ for $16$, $0$ for $17$ and $3$ for $18$. Only the prime cycles $13$ and $17$ avoid every predator cycle. This is a model, not a proof — biologists still debate the explanation.

🧪 Self-check quiz

0/5 correct

Q1. The HCF of $2^3\times3\times5^2$ and $2^2\times3^3\times7$ is

Q2. $\operatorname{LCM}(6,8)$ is

Q3. Two numbers have HCF $4$ and LCM $48$. One of them is $12$. The other is

Q4. Which of these questions needs the LCM?

Q5. Which pair cannot be the HCF and LCM (in that order) of two natural numbers?

← 1.1 The Fundamental Theorem of Arithmetic1.3 Revisiting Irrational Numbers →