HCF

1. Meaning, properties and recognition

A factor divides an integer without leaving a remainder. For example, the factors common to 18 and 30 are 1, 2, 3 and 6; therefore, their HCF is 6. The word highest is essential: several numbers may divide all the given quantities, but only one is the greatest. Every common divisor of a set of positive integers divides its HCF.

HCF questions usually involve dividing existing quantities into identical parts without any leftover. Typical expressions include greatest possible length, largest square tile, maximum number of identical groups and greatest number that divides exactly. These expressions are clues, not substitutes for reasoning. Ask whether the unknown must divide every given quantity; if it must, an HCF relationship is likely.

Useful properties reduce calculation. If one number divides another, their HCF is the smaller number. Consecutive positive integers are always coprime. Two distinct primes are coprime, but composite numbers such as 8 and 15 can also be coprime. For a positive integer k, HCF(ka, kb) = k × HCF(a, b).

• HCF(24, 72) = 24 because 24 divides 72.
• HCF(35, 36) = 1 because consecutive integers share no factor greater than 1.
• HCF(60, 84) = 12; multiplying both numbers by 5 makes their HCF 60.

2. Methods of finding the HCF

Listing factors is suitable for small integers. To find HCF(16, 24), list their factors and identify 8 as the greatest shared factor. This method is transparent but inefficient when numbers are large. In multiple-choice questions, checking the largest plausible option first can be quicker, provided the question already establishes that the unknown is a common divisor.

Prime factorisation works by expressing each number as a product of primes and selecting only the common primes, each with its smallest exponent. Thus, 72 = 2³ × 3² and 120 = 2³ × 3 × 5. Their HCF is 2³ × 3 = 24. In contrast, the LCM takes every prime appearing in either number, with its largest exponent.

Euclid's division algorithm is generally fastest for large numbers. Divide the larger number by the smaller; then divide the previous divisor by the remainder. Continue until the remainder becomes zero. The last non-zero remainder is the HCF. This works because a common divisor of a and b also divides a − qb.

For 867 and 255: 867 = 3 × 255 + 102; 255 = 2 × 102 + 51; and 102 = 2 × 51. Hence the HCF is 51. For three or more numbers, proceed pairwise: HCF(a, b, c) = HCF(HCF(a, b), c). Stop immediately if the running HCF becomes 1.

• Choose factor listing for small numbers, prime factorisation for obvious prime powers, and Euclid's algorithm for larger unfamiliar numbers.
• Verify the final result by checking that it divides every original number.

3. Equal grouping, cutting and tiling

Suppose 84 notebooks and 126 pencils must be distributed into the greatest possible number of identical kits, using everything. The number of kits must divide both quantities, so it is HCF(84, 126) = 42. Each kit contains 2 notebooks and 3 pencils. Distinguish the number of groups from the contents of each group: the HCF gives the former in this arrangement.

For cutting ropes of lengths 4.2 m, 6.3 m and 10.5 m into the longest equal pieces, first use a common unit. The lengths become 420 cm, 630 cm and 1,050 cm, whose HCF is 210 cm. The maximum piece length is therefore 2.1 m, producing 2 + 3 + 5 = 10 pieces.

A rectangular floor measuring 540 cm by 360 cm can be covered by square tiles of maximum side 180 cm, assuming tiles are aligned with the sides, no tile is cut and joint width is ignored. The number of tiles is (540 ÷ 180) × (360 ÷ 180) = 6. The HCF determines the side length, not the number or area of the tiles.

Always standardise units before calculating. Taking the HCF of 2 and 150 when the quantities are 2 metres and 150 centimetres is invalid. Also inspect the arrangement: questions permitting mixtures, wastage or unequal groups may not be direct HCF problems.

• Maximum equal piece size: calculate the HCF of the lengths.
• Maximum identical group count: calculate the HCF of the item counts.
• Number of pieces or tiles: divide the original dimensions or quantities by the HCF-derived size.

4. Divisors and remainders

If a number N leaves remainder r when divided by d, then N = qd + r, so d divides N − r. Therefore, the greatest divisor leaving specified remainders is found by taking the HCF of the adjusted numbers. A crucial condition is that every remainder must be non-negative and smaller than the divisor.

For example, find the greatest number that divides 187 and 233 leaving remainders 7 and 8 respectively. It must divide 180 and 225, so the candidate is HCF(180, 225) = 45. Since 45 exceeds both remainders, it is valid. Checking gives 187 = 4 × 45 + 7 and 233 = 5 × 45 + 8.

When several unequal numbers leave the same unspecified remainder, their differences are divisible by the required divisor. For 43, 91 and 139, the differences from 43 are 48 and 96. Their HCF is 48, and division by 48 leaves remainder 43 in all three cases. The common remainder need not be zero.

If an adjusted-number HCF is not greater than the largest specified remainder, no valid divisor exists: every other common divisor is even smaller. This check prevents a mechanically calculated but impossible answer.

• Specified remainders: subtract each remainder from its corresponding number.
• Same unspecified remainder: calculate the HCF of differences.
• Always verify the remainder condition after finding the candidate divisor.

5. HCF–LCM relationships and examination shortcuts

For exactly two positive integers, their product equals the product of their HCF and LCM. If their HCF is 12 and LCM is 180, their product is 2,160. If one number is 36, the other is 60. Do not extend this identity directly to three numbers: for 2, 4 and 8, the product is 64, whereas HCF × LCM is only 16.

If two numbers have HCF h, write them as hx and hy, where x and y are coprime. Their LCM is then hxy. With HCF 12 and LCM 180, xy = 15. The unordered coprime pairs are (1, 15) and (3, 5), giving original pairs (12, 180) and (36, 60). This method is useful when a question additionally provides a sum or difference.

HCF also simplifies fractions and ratios. Dividing 84 and 126 by their HCF, 42, reduces 84/126 to 2/3. For terminating decimals, multiply every value by the same power of ten, calculate the integer HCF and divide back by that power. Thus, HCF(1.2, 1.8) = HCF(12, 18) ÷ 10 = 0.6.

For positive fractions already in lowest terms, the usual arithmetic rule is HCF of numerators divided by LCM of denominators. Thus, the HCF of 2/3 and 4/9 is 2/9. Finally, distinguish grouping from recurrence: maximum equal divisions generally indicate HCF, while the earliest repetition or smallest common multiple generally indicates LCM.

• Check that a proposed HCF divides every number and that a proposed LCM is divisible by every number.
• Use options strategically, but do not confuse the largest listed common divisor with the true HCF unless the options support that conclusion.

Previous year questions

No UPSC question has been asked directly on this micro-topic yet. Use the practice questions below.

Practice questions