Why it matters
Two patrol jeeps leave a station together; one returns every 40 minutes, the other every 60 minutes. When are both back together? A shopkeeper packs 84 pens and 120 pencils into identical boxes with nothing left over. What is the largest number of boxes? The first question needs the LCM. The second needs the HCF.
- HCF (Highest Common Factor), also called GCD (Greatest Common Divisor): the largest number that divides each of the given numbers exactly (remainder 0).
- LCM (Least Common Multiple): the smallest number that is exactly divisible by each of the given numbers.
In the Constable written test, HCF and LCM questions are short and scoring. You can expect direct calculation, the "HCF × LCM = product" rule, remainder problems, and word problems on bells, traffic lights, tiles and containers. With the right method, most of these take 30–50 seconds.
Core concept
Level 1: Factors and multiples (beginner)
A factor of a number divides it exactly. A multiple of a number is that number times a whole number.
Factors of 12: 1, 2, 3, 4, 6, 12
Factors of 18: 1, 2, 3, 6, 9, 18
Common factors of 12 and 18: 1, 2, 3, 6 → the highest is 6, so HCF(12, 18) = 6.
Multiples of 4: 4, 8, 12, 16, 20, ...
Multiples of 6: 6, 12, 18, 24, ...
Common multiples of 4 and 6: 12, 24, 36, ... → the least is 12, so LCM(4, 6) = 12. Listing is slow for big numbers, so use the methods below.
Level 2: Prime factorisation method (intermediate)
Write each number as a product of primes using powers.
| Number | Prime factors |
|---|---|
| 24 | 2³ × 3 |
| 36 | 2² × 3² |
| 60 | 2² × 3 × 5 |
- HCF = product of the primes common to all numbers, each with its lowest power → 2² × 3 = 12.
- LCM = product of every prime that appears, each with its highest power → 2³ × 3² × 5 = 360.
Why does this work? A common factor can only use primes that every number has, and it cannot use more copies of a prime than the number with the fewest copies. A common multiple must contain every number completely, so it needs the largest number of copies of each prime.
Level 2: Division method for HCF (fast for large numbers)
Divide the larger number by the smaller. Then divide the previous divisor by the remainder. Repeat until the remainder is 0. The last divisor is the HCF.
Why does this work? If a number divides both a and b, it also divides a − b, a − 2b, and so on. So it divides the remainder too. The HCF never changes as you move down the steps, while the numbers get smaller.
Level 2: Common division (ladder) method for LCM
Divide the numbers together by a prime that divides at least two of them. Bring down any number that is not divisible. Continue until no two numbers share a factor. LCM = product of all divisors and all numbers left at the bottom.
Example: LCM of 12, 15, 20
| Divide by | 12 | 15 | 20 |
|---|---|---|---|
| 2 | 6 | 15 | 10 |
| 5 | 6 | 3 | 2 |
| 3 | 2 | 1 | 2 |
| 2 | 1 | 1 | 1 |
LCM = 2 × 5 × 3 × 2 = 60.
Level 3: Important rules (advanced)
1. Product rule (two numbers only): HCF × LCM = First number × Second number.
Check: 12 and 18 → HCF 6, LCM 36 → 6 × 36 = 216 = 12 × 18. ✔
2. HCF always divides LCM. So HCF = 15 and LCM = 100 is impossible, because 15 does not divide 100.
3. Co-prime numbers: two numbers whose HCF is 1 (like 8 and 15). Their LCM equals their product: LCM(8, 15) = 120.
4. Writing numbers using the HCF: if HCF of two numbers is H, the numbers are H × a and H × b, where a and b are co-prime. Then LCM = H × a × b.
Example: HCF = 13 and sum = 117. Then 13(a + b) = 117, so a + b = 9. Co-prime pairs: (1, 8), (2, 7), (4, 5). The pair (3, 6) is rejected because HCF(3, 6) = 3. So there are 3 such pairs: (13, 104), (26, 91), (52, 65).
5. Fractions (first write each fraction in lowest terms):
| Find | Formula |
|---|---|
| HCF of fractions | HCF of numerators ÷ LCM of denominators |
| LCM of fractions | LCM of numerators ÷ HCF of denominators |
Example: 2/3, 4/9, 8/15 → HCF = HCF(2, 4, 8) / LCM(3, 9, 15) = 2/45; LCM = LCM(2, 4, 8) / HCF(3, 9, 15) = 8/3.
6. Decimals: make the number of decimal places equal, remove the decimal point, find HCF/LCM, then put back the same decimal places.
Example: 0.6, 0.9, 1.5 → 6, 9, 15 → HCF 3, LCM 90 → HCF = 0.3, LCM = 9.0 = 9.
7. Remainder rules:
| Question says | Answer |
|---|---|
| Largest number dividing a, b, c leaving the same remainder r | HCF(a − r, b − r, c − r) |
| Largest number dividing a, b, c leaving remainders r₁, r₂, r₃ | HCF(a − r₁, b − r₂, c − r₃) |
| Largest number dividing a, b, c leaving the same (unknown) remainder | HCF of the differences (b − a), (c − b), (c − a) |
| Smallest number which, divided by x, y, z, leaves the same remainder r | LCM(x, y, z) + r |
| Smallest number which, divided by x, y, z, leaves remainders that are each k less than the divisor | LCM(x, y, z) − k |
- ✓- HCF = largest number dividing all given numbers exactly; LCM = smallest number divisible by all of them.
- ✓- Prime factorisation: HCF uses common primes with the lowest powers; LCM uses all primes with the highest powers.
- ✓- For two numbers only: HCF × LCM = product of the numbers.
- ✓- HCF always divides LCM; HCF ≤ smallest number; LCM ≥ largest number.
- ✓- Co-prime numbers: HCF = 1 and LCM = product.
- ✓- Numbers with HCF H can be written as Ha and Hb with a, b co-prime; LCM = Hab.
- ✓- Fractions: HCF = HCF(numerators)/LCM(denominators); LCM = LCM(numerators)/HCF(denominators).
- ✓- Same remainder r: largest divisor = HCF of (numbers − r); smallest number = LCM + r.
Worked examples
Example 1 (Easy): Prime factorisation
Find the HCF and LCM of 36 and 48.
- 36 = 2² × 3²; 48 = 2⁴ × 3.
- HCF: common primes 2 and 3, lowest powers → 2² × 3 = 12.
- LCM: highest powers → 2⁴ × 3² = 16 × 9 = 144.
- Check with the product rule: 12 × 144 = 1728 and 36 × 48 = 1728. ✔
Example 2 (Easy–Medium): Division method
Find the HCF of 252 and 378.
- 378 ÷ 252 = 1, remainder 126.
- 252 ÷ 126 = 2, remainder 0.
- The last divisor is 126, so HCF = 126.
Example 3 (Medium): Product rule
The HCF of two numbers is 12 and their LCM is 360. If one number is 72, find the other.
- Other number = (HCF × LCM) ÷ first number = (12 × 360) ÷ 72.
- 12 × 360 = 4320; 4320 ÷ 72 = 60.
- Check: 72 = 2³ × 3², 60 = 2² × 3 × 5 → HCF = 2² × 3 = 12 ✔, LCM = 2³ × 3² × 5 = 360 ✔.
Example 4 (Medium): Ratio given
Two numbers are in the ratio 3 : 4 and their LCM is 180. Find their HCF.
- Let the numbers be 3x and 4x. Since 3 and 4 are co-prime, HCF = x and LCM = 3 × 4 × x = 12x.
- 12x = 180 → x = 15.
- HCF = 15; the numbers are 45 and 60.
Example 5 (Medium–Hard): Bells ringing together
Three bells ring at intervals of 12, 15 and 20 minutes. They ring together at 8:00 a.m. When will they next ring together?
- They ring together after every LCM(12, 15, 20) minutes.
- LCM = 60 minutes (from the ladder table above).
- Next time together = 8:00 a.m. + 60 minutes = 9:00 a.m.
Example 6 (Hard): Remainder type (HCF)
Find the largest number that divides 245 and 1029 leaving remainder 5 in each case.
- Remove the remainder: 245 − 5 = 240 and 1029 − 5 = 1024. The required number divides both exactly.
- 240 = 2⁴ × 3 × 5; 1024 = 2¹⁰.
- HCF = 2⁴ = 16.
- Check: 16 × 15 = 240, so 245 leaves 5 ✔; 16 × 64 = 1024, so 1029 leaves 5 ✔.
Example 7 (Exam-hard): Remainder type (LCM)
Find the smallest number which, when divided by 12, 16 and 18, leaves remainders 8, 12 and 14 respectively.
- Look at the gaps: 12 − 8 = 4, 16 − 12 = 4, 18 − 14 = 4. Each remainder is 4 less than its divisor.
- So the number + 4 is divisible by 12, 16 and 18.
- LCM(12, 16, 18): 12 = 2² × 3, 16 = 2⁴, 18 = 2 × 3² → 2⁴ × 3² = 144.
- Required number = 144 − 4 = 140.
- Check: 140 = 12 × 11 + 8 ✔; 140 = 16 × 8 + 12 ✔; 140 = 18 × 7 + 14 ✔.
Real-world connection
- Cutting and tiling (HCF): A hall floor is 6 m 24 cm long and 4 m 32 cm wide. To cover it with the largest possible identical square tiles, convert to cm: 624 and 432. HCF(624, 432) = 48 (624 − 432 = 192; 432 = 2 × 192 + 48; 192 = 4 × 48). So each tile is 48 cm, and the number of tiles = (624 ÷ 48) × (432 ÷ 48) = 13 × 9 = 117.
- Packing (HCF): 84 pens and 120 pencils go into the greatest number of identical boxes → HCF(84, 120) = 12 boxes, each with 7 pens and 10 pencils.
- Schedules (LCM): traffic signals changing every 30, 45 and 60 seconds, buses leaving a depot every 20 and 25 minutes, or patrol jeeps returning every 40 and 60 minutes all meet again after the LCM (180 seconds, 100 minutes and 120 minutes respectively).
- Using the product rule for three numbers. HCF × LCM = product is true only for two numbers. For 2, 4, 8: HCF 2 × LCM 8 = 16, but 2 × 4 × 8 = 64.
- Mixing up powers. HCF takes the lowest power of common primes; LCM takes the highest power of all primes. Swapping them is the most common wrong answer, and it is always among the options.
- Choosing HCF when the question needs LCM (or the reverse). "Largest size / greatest number that divides" → HCF. "Smallest number divisible by / next time together" → LCM. Read what is being asked, not just the word "largest" or "smallest".
- Forgetting to convert units. 6 m 24 cm and 4 m 32 cm must both be in cm before finding the HCF.
- Counting the start time in bell problems. If bells ring together every 60 minutes, then in 3 hours they ring together 3 times after the start, or 4 times including the start. Check which the question wants.
- Check options backwards: the HCF must divide every given number; the LCM must be divisible by every given number. Strike out options that fail — often only one survives.
- Size check: HCF can never be larger than the smallest number; LCM can never be smaller than the largest number.
- Ratio shortcut: numbers in ratio a : b (a, b co-prime) → HCF = x, LCM = abx.
- Remainder shortcut: if each remainder is k less than its divisor, answer = LCM − k. If all remainders are equal to r, answer = LCM + r.
- Divide only once for a quick HCF: HCF of two numbers also divides their difference. HCF(391, 437) must divide 46 = 2 × 23; 23 divides both (391 = 23 × 17, 437 = 23 × 19), so the HCF is 23.
- Mnemonic — "HCF goes LOW, LCM goes HIGH": for HCF take the low powers of shared primes; for LCM take the high powers of every prime.
How it is asked in the exam
Each question gets about 54 seconds on average, and there is no negative marking, so never leave one blank. Aim to finish these faster to save time for longer topics.
Common formats: direct HCF/LCM of two or three numbers; product rule (find the other number or the LCM); ratio with HCF or LCM; remainder problems; bells, lights and buses ("when together again?"); tiles, rods and containers ("largest size"); fractions or decimals; least or greatest 4-digit number divisible by given numbers.
Difficulty levels:
- Easy (about 20–30 s): LCM of 8, 12 and 18 → 72.
- Medium (about 40 s): product of two numbers is 2160 and HCF is 12 → LCM = 2160 ÷ 12 = 180.
- Hard (about 60 s): least 4-digit number divisible by 12, 15 and 20. LCM = 60; 1000 ÷ 60 gives quotient 16 and remainder 40, so take the next multiple: 60 × 17 = 1020.
- Find the HCF and LCM of 18, 24 and 30.
Answer: 18 = 2 × 3², 24 = 2³ × 3, 30 = 2 × 3 × 5 → HCF = 2 × 3 = 6; LCM = 2³ × 3² × 5 = 360. - Can two numbers have HCF 15 and LCM 100?
Answer: No. The HCF must divide the LCM, and 15 does not divide 100. - The product of two numbers is 2160 and their HCF is 12. Find their LCM.
Answer: 2160 ÷ 12 = 180. - What is the smallest number exactly divisible by 8, 12 and 15?
Answer: LCM = 2³ × 3 × 5 = 120.
- ✓- HCF = biggest common divisor; LCM = smallest common multiple.
- ✓- Prime factors: HCF → lowest powers of common primes; LCM → highest powers of all primes.
- ✓- Division method: keep dividing by the remainder; the last divisor is the HCF.
- ✓- Two numbers only: HCF × LCM = product. HCF always divides LCM.
- ✓- Co-prime numbers: HCF 1, LCM = product. Ratio a : b → HCF x, LCM abx.
- ✓- Same remainder r: largest divisor = HCF(numbers − r); smallest number = LCM + r; remainders k short of divisors → LCM − k.
- ✓- Fractions: HCF = HCF(num)/LCM(den); LCM = LCM(num)/HCF(den).
- ✓- "Largest size / divides" → HCF; "next together / divisible by" → LCM.
తెలుగు సారాంశం (Telugu summary)
గ.సా.భా (HCF) అంటే ఇచ్చిన అన్ని సంఖ్యలను శేషం లేకుండా భాగించే అతిపెద్ద సంఖ్య. క.సా.గు (LCM) అంటే ఇచ్చిన అన్ని సంఖ్యలతో శేషం లేకుండా భాగించబడే అతిచిన్న సంఖ్య.
ప్రధాన కారణాంకాల పద్ధతిలో, గ.సా.భా కోసం ఉమ్మడి ప్రధాన కారణాంకాల కనిష్ఠ ఘాతాలను తీసుకోవాలి; క.సా.గు కోసం అన్ని ప్రధాన కారణాంకాల గరిష్ఠ ఘాతాలను తీసుకోవాలి.
పెద్ద సంఖ్యలకు భాగహార పద్ధతి వేగంగా ఉంటుంది: శేషం సున్నా వచ్చే వరకు భాగిస్తూ ఉండాలి, చివరి భాజకమే గ.సా.భా.
రెండు సంఖ్యలకు మాత్రమే: గ.సా.భా × క.సా.గు = ఆ రెండు సంఖ్యల లబ్ధం. మూడు సంఖ్యలకు ఈ సూత్రం వర్తించదు.
గ.సా.భా ఎల్లప్పుడూ క.సా.గు ను భాగిస్తుంది. పరస్పర ప్రధాన సంఖ్యల గ.సా.భా 1, వాటి క.సా.గు వాటి లబ్ధానికి సమానం.
ప్రతిసారి ఒకే శేషం r మిగలాలంటే: అతిపెద్ద భాజకం = (సంఖ్యలు − r) యొక్క గ.సా.భా; అతిచిన్న సంఖ్య = క.సా.గు + r.
భిన్నాల గ.సా.భా = లవాల గ.సా.భా ÷ హారాల క.సా.గు; భిన్నాల క.సా.గు = లవాల క.సా.గు ÷ హారాల గ.సా.భా.
"అతిపెద్ద పరిమాణం", "అన్నింటినీ భాగించే" అనే మాటలు ఉంటే గ.సా.భా; "మళ్ళీ ఎప్పుడు కలిసి", "అన్నింటితో భాగించబడే" అనే మాటలు ఉంటే క.సా.గు.
Key terms (English — తెలుగు):
- HCF / GCD — గరిష్ఠ సామాన్య భాజకం (గ.సా.భా)
- LCM — కనిష్ఠ సామాన్య గుణిజం (క.సా.గు)
- Factor — కారణాంకం
- Multiple — గుణిజం
- Prime factorisation — ప్రధాన కారణాంకాలుగా విభజన
- Co-prime numbers — పరస్పర ప్రధాన సంఖ్యలు
- Divisor — భాజకం
- Remainder — శేషం
- Numerator — లవం
- Denominator — హారం
- Product — లబ్ధం