Question

Use Euclid’s division algorithm to find the HCF of:
135 and 225

Answer 1

Hint: We solve this problem by using Euclid’s division of finding the HCF.
We use the normal division method to the given numbers and represent the largest number225 in terms of 135 that is
\[225=\left( 135\times p \right)+q\]
Then we use the same process for 135 and \[q\] until we get 0 as the remainder. Then the divisor used at that division can be concluded as the HCF

Complete step by step answer:
We are asked to find the HCF of 135 and 225 using Euclid’s division.
We know that the steps involved in Euclid’s division are
(1) We divide the large number with a small number and take the remainder.
(2) Next we divide the divisor used in the previous division with the remainder we got in the previous division and take the remainder.
(3) We carry out step (2) until we get the remainder as 0.
(4) The divisor used when the remainder is 0 will be the HCF of the given two numbers.
Now, let us apply the first step that is let us divide the number 225 with 135 then we get
\[\Rightarrow 225=\left( 135\times 1 \right)+90\]
Here we can see that the divisor used in the previous division is 135 and the remainder is 90
Now, let us apply the second step that is let us divide the number 135 with 90 then we get
\[\Rightarrow 135=\left( 90\times 1 \right)+45\]
Here we can see that the divisor used in the previous division is 90 and the remainder is 45
Now, let us apply the second step that is let us divide the number 90 with 45 then we get
\[\Rightarrow 90=\left( 45\times 2 \right)+0\]
Here we can see that we got the remainder in the previous division as 0 when the divisor is 45
Now, let us apply the fourth step that is the divisor used to get the remainder 0 is the HCF
Therefore we can conclude that the HCF of 135 and 225 is 45
\[\therefore HCF\left( 135,225 \right)=45\]

Note:
We can solve this problem by using different methods like the prime factorization method.
We get the same answer in any method we use. But in this problem, we are asked to solve the question using Euler’s division method.
So, we need to use the same method for solving the problem. Students may use other types also but which will not be the correct solution for this problem.
There is one more important point in which students may do mistakes.
In the second step, we divide the divisor used in the previous division with the remainder.
But some students do this division by taking the quotient and the divisor. That is they divide the divisor with quotient.
This gives the wrong answer because Euclid’s division is t defined in this way.