Question

Use Euclid’s algorithm to find HCF of 455 and 42.

Answer 1

Hint:
Here, we apply the Euclid algorithm to find the HCF of 455 and 42.
First, we can also write 445 as $42 \times 10 + 35$
After that, use the Euclid algorithm on 42 and 3. Again, we will apply the Euclid algorithm on 35 and 7.
Finally, after solving this we will get the answer.

Complete step by step solution:
Euclid’s Algorithm: Euclid’s Algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers, the largest number that divides them both without a remainder.
For example: 69 can be written by Euclid’s Algorithm as
 $69 = 6 \times 10 + 9$ .
Here, first we can write 455 as,
 $445 = 42 \times 10 + 35$
Now, by using Euclid algorithm on 42 and 35, we get,
 $42 = 35 \times 1 + 7$
Again, we apply Euclid algorithm on 35 and 7, so we get,
 $35 = 7 \times 5 + 0$
So, here we the remainder as zero that mean we will stop applying the Euclid algorithm.
 $ \Rightarrow $ The last non-zero remainder is 7

$ \Rightarrow $ The HCF of 455 and 42 is 7.

Note:
In this confusion arises what would be the HCF of two numbers if the zero remainder is obtained in the first step. In this type of case, the smaller value of the two numbers is their HCF.