Question

Find the HCF of 32 and 616 by prime factorisation method and Euclid division algorithm

Answer 1

By Euclid division lemma algorithm:

Step 1: Since 616 > 32, we apply the division lemma to 616 and 32, to get

616 = 32 x 19 + 8

Step 2: Since the reminder 32 ≠ 0, we apply division lemma to 8 and 32, to get

32 = 8 x 4 + 0

The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 8, the HCF of 616 and 32 is 8

Notice that 8 = HCF(32,8) = HCF(616,32) .

And, By prime factorization method:

Prime factorization of 616 and 32 is (2 × 2 × 2 × 7 × 11) and (2 × 2 × 2 × 2 × 2) respectively. As visible, 616 and 32 have common prime factors. Hence, the HCF of 616 and 32 is 2 × 2 × 2 = 8.