JEE Mathematics HCF and LCM Notes Set 01

Factors, Common Factors and H.C.F.

A common factor of two numbers divides both. The highest common factor (H.C.F., also called G.C.D. or G.C.M.) of two or more numbers is the greatest number that divides each of them exactly. Two numbers whose H.C.F. is 1 are called co-prime. If a number divides two numbers it divides their sum and their difference, and more generally any combination ma + nb.

Finding the H.C.F.

1. Prime factorisation: write each number as a product of primes and take every common prime with its lowest power. Example: \( 450=2\cdot3^2\cdot5^2 \), \( 825=3\cdot5^2\cdot11 \), \( 7875=3^2\cdot5^3\cdot7 \) give H.C.F. \( 3\cdot5^2=75 \).
2. Division method: divide the larger number by the smaller, then divide the divisor by the remainder, and repeat until the remainder is 0. The last divisor is the H.C.F. Example: 1147 = 2 x 527 + 93, 527 = 5 x 93 + 62, 93 = 1 x 62 + 31, 62 = 2 x 31, so H.C.F. = 31.
3. For three numbers, find the H.C.F. of two and then the H.C.F. of that result with the third. First pull out any obvious common factor (digit sums for 3 and 9, last digits for 2 and 5) to shorten the work.
4. If the H.C.F. comes out as 1 (for example 219 and 8399), the numbers are co-prime.

Finding the L.C.M.

1. The lowest common multiple (L.C.M.) is the smallest number that every given number divides. Using primes, take every prime that appears, each with its highest power. Example: 96, 100, 120, 144 give \( 2^5\cdot3^2\cdot5^2=7200 \).
2. Short division: write the numbers in a row, divide by a prime that divides at least two of them (carry the others down unchanged), repeat until no prime divides two numbers. The L.C.M. is the product of all divisors and the remaining numbers. Example: 12, 28, 63, 70, 84 give 1260.
3. For co-prime numbers the L.C.M. is the product.

Relation Between H.C.F. and L.C.M.

For two numbers p and q: \( \text{H.C.F.}\times\text{L.C.M.}=p\times q \). Proof idea: if the H.C.F. is m then \( p=mx \) and \( q=my \) with x and y co-prime, so the L.C.M. is mxy and \( pq=m^2xy=m\cdot mxy \). Example: H.C.F. of 817 and 2021 is 43, so the L.C.M. is \( \frac{817\times2021}{43}=38399 \). This relation holds only for two numbers.

Fractions

H.C.F. of fractions in lowest terms is (H.C.F. of numerators) / (L.C.M. of denominators). L.C.M. of fractions is (L.C.M. of numerators) / (H.C.F. of denominators).

Typical Word Problems

Example: three runners take 252 s, 308 s and 198 s per round. They are together at the start again after L.C.M. = 2772 s, when they have completed 11, 9 and 14 rounds.