HCF and LCM: Methods, Tricks, and Verified Placement Examples

HCF and LCM are the two sides of the same divisibility coin, and most placement aptitude tests include at least two questions on them.

The TCS NQT Numerical Ability section and the AMCAT quantitative aptitude module both test HCF and LCM regularly, usually as word problems or as direct computation questions. Mastering two methods for each is sufficient. This article covers both methods for HCF and LCM, flags a widely circulated wrong answer in legacy prep content, and closes with six placement-style examples re-derived from scratch.

What HCF and LCM Actually Mean

The Highest Common Factor (HCF), also called the Greatest Common Divisor (GCD), is the largest positive integer that divides every number in a set without leaving a remainder.

The Least Common Multiple (LCM) is the smallest positive integer that is divisible by every number in the set.

The Product Relationship

For any two numbers A and B:

• A × B = HCF(A, B) × LCM(A, B)

This means if you know three of the four values, the fourth follows directly. The rule applies to exactly two numbers. For three or more numbers, there is no analogous product formula.

Co-prime Numbers

Two numbers are co-prime if their HCF is 1. For co-prime pairs, LCM equals their product.

• HCF(8, 15) = 1, so LCM(8, 15) = 8 × 15 = 120.

HCF and LCM of Fractions

• HCF of fractions = HCF of numerators / LCM of denominators
• LCM of fractions = LCM of numerators / HCF of denominators

Finding HCF: Prime Factorization and the Euclidean Method

Prime Factorization Method

Express each number as a product of prime powers. The HCF is the product of the lowest powers of primes shared by every number.

Example: Find the HCF of 96, 144, and 240.

• Step 1: Factorise each number.
  • 96 = 2^5 × 3^1
  • 144 = 2^4 × 3^2
  • 240 = 2^4 × 3^1 × 5^1
• Step 2: Identify primes common to all three: 2 and 3 (5 appears only in 240).
• Step 3: Take the lowest power of each common prime.
  • Lowest power of 2: 2^4 (from 144 and 240)
  • Lowest power of 3: 3^1 (from 96 and 240)
• Step 4: HCF = 2^4 × 3^1 = 16 × 3 = 48
• Verification: 96/48 = 2, 144/48 = 3, 240/48 = 5 (all exact).

Euclidean Division Method

Divide the larger number by the smaller, replace the larger with the smaller and the smaller with the remainder, and repeat until the remainder is 0. The last non-zero remainder is the HCF.

Example: Find the HCF of 144 and 96.

• Step 1: 144 ÷ 96 = 1 remainder 48
• Step 2: 96 ÷ 48 = 2 remainder 0
• HCF = 48

For three or more numbers, find the HCF of the first two, then find the HCF of that result and the third number.

The Euclidean algorithm runs in O(log n) time. It is a standard implementation question in entry-level coding rounds, so understanding its mechanics serves both aptitude and technical interview prep.

A Shortcut for HCF — and When It Fails

The difference shortcut: the HCF of two numbers always divides their difference. So if two numbers differ by d, the HCF is either d itself or a factor of d. Test whether d divides all given numbers; if not, factor d and test each factor.

When the Shortcut Works

Example: HCF of 12 and 16.

• Difference = 16 - 12 = 4
• Does 4 divide 12? Yes (12/4 = 3). Does 4 divide 16? Yes (16/4 = 4).
• HCF = 4.

Example: HCF of 18 and 22.

• Difference = 22 - 18 = 4
• Does 4 divide 18? No (18/4 = 4.5).
• Factor 4: factors are 1, 2, 4. Try 2: does 2 divide 18? Yes. Does 2 divide 22? Yes.
• HCF = 2.

Example: HCF of 15, 25, and 35.

• Differences: 25 - 15 = 10, 35 - 25 = 10.
• Does 10 divide 15? No (15/10 = 1.5).
• Factor 10: try 5: does 5 divide 15, 25, and 35? Yes (15/5=3, 25/5=5, 35/5=7).
• HCF = 5.

When the Shortcut Breaks

The shortcut fails when the difference does not directly divide all numbers and the factoring step still leaves ambiguity, or when numbers have more than two distinct pairwise differences. In those cases, prime factorization or the Euclidean method is the reliable path.

Finding LCM: Prime Factorization and the Scan Method

Prime Factorization Method

Factorise all numbers. The LCM is the product of the highest powers of all primes appearing in any of the numbers.

Example: Find the LCM of 96, 144, and 240.

• Factorisations:
  • 96 = 2^5 × 3^1
  • 144 = 2^4 × 3^2
  • 240 = 2^4 × 3^1 × 5^1
• Highest power of 2: 2^5 (from 96)
• Highest power of 3: 3^2 (from 144)
• Highest power of 5: 5^1 (from 240)
• LCM = 2^5 × 3^2 × 5^1 = 32 × 9 × 5 = 1440

Divisibility Scan Method

If the largest number in the set is divisible by all the others, it is the LCM. If not, multiply it by 2, then 3, and so on until you find a multiple divisible by every number.

Example: LCM of 2, 4, 8, and 16.

• Largest = 16. Is 16 divisible by 2, 4, and 8? Yes.
• LCM = 16.

Example: LCM of 2, 3, 7, and 21.

• Largest = 21. Is 21 divisible by 2? No (21/2 = 10.5).
• Try 21 × 2 = 42. Is 42 divisible by 2, 3, 7, and 21? Yes (42/2=21, 42/3=14, 42/7=6, 42/21=2).
• LCM = 42.

A Common Mistake Corrected

Many legacy prep guides claim LCM(12, 36, 60, 108) = 108. That is wrong. Check: 108 ÷ 60 = 1.8, which is not a whole number, so 108 cannot be the LCM.

Correct derivation for LCM of 12, 36, 60, and 108:

• 12 = 2^2 × 3^1
• 36 = 2^2 × 3^2
• 60 = 2^2 × 3^1 × 5^1
• 108 = 2^2 × 3^3
• Highest powers: 2^2, 3^3, 5^1
• LCM = 4 × 27 × 5 = 540

The scan method fails here because none of the first few multiples of 108 (216, 324, 432) are divisible by 60. The correct answer is 540.

HCF and LCM of Fractions

Using the fraction formulas stated in the first section:

Example: HCF of 2/3, 4/9, and 8/27.

• HCF of numerators: HCF(2, 4, 8) = 2
• LCM of denominators: LCM(3, 9, 27) = 27
• HCF = 2/27

Example: LCM of 2/3, 4/9, and 8/27.

• LCM of numerators: LCM(2, 4, 8) = 8
• HCF of denominators: HCF(3, 9, 27) = 3
• LCM = 8/3

Six Placement-Style Problems — Verified Solutions

These cover the main question types in TCS NQT and AMCAT.

• Q1. The HCF of two numbers is 8 and their LCM is 96. One number is 24. Find the other.

  • Using the product relationship: 24 × other = 8 × 96 = 768
  • Other = 768/24 = 32

• Q2. Find the largest number that divides 56, 84, and 112 exactly.

  • This is an HCF question.
  • HCF(56, 84): 84 ÷ 56 = 1 remainder 28; 56 ÷ 28 = 2 remainder 0. HCF = 28.
  • HCF(28, 112): 112 = 28 × 4, remainder 0. HCF = 28.
  • Answer: 28

• Q3. Three bells ring every 12, 18, and 24 minutes. They ring together at 8:00 AM. When do they next ring together?

  • Find LCM(12, 18, 24).
  • 12 = 2^2 × 3, 18 = 2 × 3^2, 24 = 2^3 × 3
  • LCM = 2^3 × 3^2 = 72
  • Answer: 72 minutes after 8:00 AM = 9:12 AM

• Q4. Find the smallest number exactly divisible by 15, 20, and 36.

  • LCM question: 15 = 3 × 5, 20 = 2^2 × 5, 36 = 2^2 × 3^2
  • LCM = 2^2 × 3^2 × 5 = 180
  • Answer: 180

• Q5. The LCM of two numbers is 45 times their HCF. The sum of the HCF and LCM is 1,150. One number is 45. Find the other.

  • Let HCF = h, LCM = 45h.
  • h + 45h = 1,150, so 46h = 1,150, giving h = 25.
  • LCM = 45 × 25 = 1,125.
  • Other = (HCF × LCM) / first = (25 × 1,125) / 45 = 625.
  • Answer: 625

• Q6. Find the HCF and LCM of 1/2, 3/4, and 5/6.

  • HCF = HCF(1, 3, 5) / LCM(2, 4, 6) = 1/12
  • LCM = LCM(1, 3, 5) / HCF(2, 4, 6) = 15/2

The Euclidean algorithm for HCF, which this article covers in the second section, is also a common coding-round implementation question. For the coding layer that builds on the same integer-math foundations, TinkerLLM starts at ₹299 and covers algorithmic problem-solving from first principles.

For other modular-arithmetic and time-based aptitude topics tested in the same exam sections, see the clock problems guide and the calendar problems walkthrough.