Application of lemma

Euclid’s Division lemma is used to find HCF of two positive integers.

Example: Find HCF of 56 and 72?
Steps:

  • Apply lemma to 56 and 72.
  • Take bigger number and locate ‘b’ and ‘r’. 72 = 56 \times 1 + 16
  • Since 16  \ne 0, consider 56 as the new dividend and 16 as the new divisor.56 = 16 \times 3 + 8
  • Again, 8 \ne 0, consider 16 as new dividend and 8 as new divisor.16 = 8 \times 2 + 0

Since remainder is zero, divisor (8) is HCF.

Constructing a factor tree

  • Write the number as a product of prime number and a composite number
    Example:
    Factorize 48
  • Repeat the process till all the primes are obtained
    ∴ Prime factorization of 48 = {2^4} \times 3
Scroll to Top