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’.
• Since 16 0, consider 56 as the new dividend and 16 as the new divisor.
• Again, 8 0, consider 16 as new dividend and 8 as new divisor.

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