HCF and LCM

1. HCF (Highest Common Factor) or GCD (Greatest Common Divisor)

• Definition:

  • The HCF of two or more numbers is the largest positive integer that divides each of the numbers evenly (without leaving a remainder).

  • It's the largest common factor among the given numbers.

• Methods to Find HCF:

  • Prime Factorization Method:

    1. Find the prime factors of each number.

    2. Identify the common prime factors among all the numbers.

    3. Find the product of the common prime factors with the lowest power.

  • Euclidean Algorithm:

    1. Divide the larger number by the smaller number.

    2. If there's a remainder, divide the smaller number by the remainder.

    3. Repeat step 2 until the remainder is 0.

    4. The last divisor is the HCF.

2. LCM (Least Common Multiple)

• Definition:

  • The LCM of two or more numbers is the smallest positive integer that is a multiple of all the given numbers.

  • It's the smallest number that is divisible by all the given numbers.

• Methods to Find LCM:

  • Prime Factorization Method:

    1. Find the prime factors of each number.

    2. Identify all the prime factors that appear in any of the numbers.

    3. For each prime factor, select the highest power it appears in any of the numbers.

    4. Find the product of all the selected prime factors with their respective highest powers.

  • Listing Multiples Method:

    1. List the multiples of each number.

    2. Find the smallest common multiple among the lists. (This method can be time-consuming for larger numbers)

3. Relationship between HCF and LCM

• For two numbers 'a' and 'b':

  • Product of the numbers = HCF(a, b) * LCM(a, b)

Applications of HCF and LCM:

• Simplifying fractions: Finding the HCF of the numerator and denominator.

• Solving word problems:

  • Finding the time when events will happen simultaneously.

  • Determining the length of the shortest piece when cutting objects into equal parts.

  • Scheduling tasks that repeat at regular intervals.

Example:

Find the HCF and LCM of 12 and 18.

• Prime Factorization:

  • 12 = 2 * 2 * 3

  • 18 = 2 * 3 * 3

• HCF:

  • Common prime factors: 2 and 3

  • HCF = 2 * 3 = 6

• LCM:

  • All prime factors: 2, 3

  • Highest powers: 2² (from 12), 3² (from 18)

  • LCM = 2² * 3² = 4 * 9 = 36