Question

Using Euclid’s division algorithm, find the H.C.F. of 135 and 714.

Answer 1

Hint: Euclid’s division Algorithm is a method of finding the greatest common divisor of two numbers by dividing the larger by the smaller, the smaller by the remainder, the first remainder by the second remainder, and so on until exact division is obtained whence the greatest common divisor is the exact divisor.

Complete step-by-step answer:
We have to find the H.C.F. of 135 and 714 using Euclid’s division algorithm.
So, since 714 > 135, apply the algorithm to 714 and 135
$714 = 135 \times 5 + 39$
Now, since $39 \ne 0$, apply the division algorithm to 135 and 39
$135 = 39 \times 3 + 18$
Now, since $18 \ne 0$, apply the division algorithm to 39 and 18
$39 = 18 \times 2 + 3$
Now, since $3 \ne 0$, apply the division algorithm to 18 and 3
$18 = 3 \times 6 + 0$
The remainder has now become zero, so we will stop applying the algorithm.
Since, the divisor in the last step is 3, hence the H.C.F. of 714 and 135 is 3.

Note: Whenever we face such types of problems the key point to remember is that we need to have a good grasp over Real Numbers and Euclid’s division algorithm. In these types of questions, we should never miss any step and show every step while applying the algorithm.