Summary: Hcf Lcm
CSAT Angle
The topic is repeatedly asked in CSAT papers. Mastering HCF and LCM helps solve many numeracy questions, especially those on timing and repeated events.
Factors
A composite number N can be written as a product of prime powers: N = xa × yb × zc ... . The prime numbers in this factorisation are the prime factors. The total number of factors of N (including 1 and N) = (a+1)(b+1)(c+1)...
Multiples
A multiple of N is any number divisible by N. A common multiple of numbers is a number divisible by each of them. The Least Common Multiple (LCM) is the smallest such common multiple.
Methods of Finding LCM
- By factorisation: write each number as prime powers, take all prime factors that appear, and raise each to the highest power occurring among the numbers; product gives the LCM.
- By division method: divide the set of numbers repeatedly by smallest possible primes until all quotients are 1; product of the divisors gives the LCM. Ensure numbers use same units before starting.
Co-primes
Two numbers are co-primes if their HCF is 1.
Applications of LCM
- Time after which repeating events coincide (e.g., bells, runners) = LCM of their intervals.
- Finding common schedules or synchronized occurrences uses LCM.
Common Factor
A common factor of numbers is a number dividing each of them exactly.
Highest Common Factor (HCF)
The HCF (also called GCD) of numbers is the largest number that divides each exactly.
Methods of Finding HCF
- Factorisation method: express each number as prime factors; take product of common primes with their lowest powers.
- Division method: apply repeated division (Euclidean method): divide larger by smaller, replace pair by (divisor, remainder) until remainder is 0; last nonzero divisor is HCF.
- Prime factorisation (factor tree): break each number into primes, identify common primes and multiply them (use minimum powers) to get HCF.
Properties of LCM and HCF
- The least number exactly divisible by a, b, c is their LCM.
- The greatest number that divides a, b, c is their HCF.
- HCF of given numbers is a factor of their LCM.
Relationship between HCF and LCM
For two numbers P and Q: GCD(P, Q) × LCM(P, Q) = P × Q. (This rule applies only to two numbers.)
HCF and LCM of Decimals
- Convert all decimals to like decimals by annexing zeros.
- Remove decimal points and find HCF/LCM of the resulting integers.
- Restore the decimal point in the final answer according to the total decimal places used.
HCF and LCM of Fractions
Find HCF and LCM of fractions by treating numerators and denominators separately: compute HCF or LCM of numerators and denominators, then form the fraction (and simplify if needed).
HCF and LCM of Polynomials
- HCF of polynomials: a common factor polynomial that divides each polynomial.
- LCM of polynomials: the least-degree polynomial divisible by each given polynomial.
Common Applications of HCF and LCM
- Greatest number dividing x, y, z leaving remainders a, b, c = HCF of (x-a), (y-b), (z-c).
- Greatest number dividing x, y, z leaving the same remainder in each case = HCF of differences like (x-y), (y-z), (z-x).
- Least number which when divided by x, y, z leaves remainders a, b, c respectively = LCM(x, y, z) - k, where k = common value of (x-a) = (y-b) = (z-c).
- Least number which when divided by x, y, z leaves the same remainder k = LCM(x, y, z) + k.
