Question

Find the HCF of 867 and 255, using Euclid’s Division Algorithm.

Answer 1

Hint: We will be using the Euclid division algorithm to solve the problem. We know that this algorithm is the process of applying Euclid division lemma in succession several times to obtain the HCF of any two numbers. Euclid’s division lemma states that we can write a number as multiple of any other number plus the remainder obtained by dividing the number with the other number.
Complete step-by-step answer:
Now, we have to find the HCF of 867 and 255, using Euclid’s Division Algorithm.
Now, understand the Euclid division algorithm. We first suppose two numbers a and b.
Now, applying Euclid division lemma we will have two integer a and r such that
$a=b\left( q \right)+r$
Now, here q is quotient and r is remainder. Now we have to notice an important fact related to this equation that any common factor of a and b must also be a factor of r. For example, if k is a common factor of a and b then,
$\begin{align}
  & \dfrac{a}{k}=\dfrac{b}{k}\left( q \right)+\dfrac{r}{k} \\
 & \dfrac{a}{k}-\dfrac{b}{k}\left( q \right)=\dfrac{r}{k} \\
\end{align}$
Now, since the left side is an integer. Therefore, for the right side to be integer r must be divisible by k.
Now, we have two numbers 867 and 255. So, we can write,
$867=255\left( 3 \right)+102\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ step-1$
Now, on the basis of the Euclid division algorithm, if the HCF (call it x) is a factor of 867 and 255, it must also be a factor of the remainder. So, again we apply division lemma.
$255=102\left( 2 \right)+51\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ step-2$
Now, again we apply Euclid division lemma. So, we have,
$102=51\times 2+0$
Now, we have no remainder left. Therefore, the second last remainder is HCF that is HCF (867, 255) = 51.

Note: To solve this question it is important to note the way we have used Euclid division lemma repeatedly to solve the problem. Also, it is important to note that if two numbers have a common factor then their remainder will also have the same factor as we have used to find the HCF of two numbers with the help of Euclid Division Algorithm.