Question

Using Euclid’s division algorithm, find the H.C.F of 56, 96 and 404.

Answer 1

Hint: The given problem is related to Euclid’s division algorithm. In Euclid’s division algorithm, we use the fact that the common factor of two numbers should also be the factor of the remainder obtained on dividing one of the given numbers by the other. First, we will find the HCF of 56 and 96 (say x), then we will find the HCF of x and 404. The HCF of x and 404 will be the HCF of 56, 96, and 404.

Complete step-by-step solution -
Before proceeding with the solution, let’s understand Euclid’s division algorithm. The Euclid’s division lemma states that if there are two numbers a and b, then there exists a unique pair of integers q and r satisfying a = bq + r, where $0\le r<b$ . The Euclid’s division algorithm uses this lemma to determine the HCF of two numbers a and b. The algorithm uses the theorem that if a = bq + r , then the common divisor of a and b must be the common divisors of b and r.
In the given question, we are asked to find the HCF of 56, 96, and 404. First, we will find the HCF of 56 and 96 (say x), then we will find the HCF of x and 404. The HCF of x and 404 will be the HCF of 56, 96, and 404.
By Euclid’s division lemma, we can write $96=(56\times 1)+40$ . Since the HCF is a factor of both 56 and 96, it must be a factor of 56 and 40. Now, we will apply the lemma on 56 and 40. So, $56=(40\times 1)+16$ . Again, the HCF must be a factor of 16 and 40. Applying the lemma on 16 and 40, we get $40=(16\times 2)+8$ . Since HCF is a factor of 16 and 40, it must also be a factor of 16 and 8. Again, using the lemma on 16 and 8, we get $16=(8\times 2)+0$ . Here, the remainder is 0. So, the HCF of 96 and 56 is 8, i.e. x=8.
Now, we will find the HCF of 404 and 8 using Euclid’s division algorithm. We can write 404 as $$404=(8\times 50)+4$$ . Since the HCF is a factor of 404 and 8, it must also be a factor of 8 and 4. So, applying the lemma on 8 and 4, we get $8=(4\times 2)+0$ . Here, the remainder is equal to 0. So, the HCF of 8 and 404 is 4. Since 8 is the HCF of 56 and 96, hence, the HCF of 56, 96, and 404 is 4.

Note: While using the lemma, be careful while doing calculations and make sure that the value of the remainder should always be less than the divisor. If the value of the remainder is being calculated as greater than the divisor, then there must be some mistake in the calculation.