Question

What is the HCF of 867 and 255 using the Euclid theorem?

A.50

B.51

C.52

D.53

Answer 1

Hint: HCF of two numbers is the largest number exactly dividing the two numbers. We are going to use the step by step procedure of Euclid's division algorithm using the division lemma. 

According to Euclid’s division lemma, the HCF of any two positive integers $a$ and $b$, with $a > b$, is obtained as follows:

Step 1: Apply the division lemma to find $q$ and $r$ where $a = bq + r$ ,$0 \leqslant r < b$.

Step 2: if $r = 0$, the HCF is $b$. If $r \ne 0$, apply Euclid’s lemma to $b$ and $r$.

Step 3: Continue the process till the remainder is zero. The divisor at this stage will be the HCF of $a$ and $b$.

Complete step-by-step answer:

The largest positive integer which divides two or more integers without any remainder is called the Highest Common Factor (HCF) or Greatest Common Divisor or Greatest Common Factor (GCF).

We can find the HCF of two numbers using Euclid’s division algorithm.

Given the problem, we need to find HCF of $867$ and $255$ using Euclid's division algorithm.

Using the above steps with $a = 867$ and $b = 255$ because $867 > 255$, hence $a > b$.

Using division lemma on $a = 867$, we get

$  867 = bq + r = 255 \times 3 + 102 $, here $ b = 255,q = 3,r = 102 $ Remainder is not zero. So, we proceed further till $r=0$.

Applying Euclid’s lemma to $b$ and $r$, we get

\[  255 = 102 \times 2 + 51  \], \[   b = 102,q = 2,r = 51 \] 

Again, since $r \ne 0$, applying Euclid’s lemma to $b$ and $r$ and continuing the same step till we get $r = 0$.

\[  102 = 51 \times 2 + 0 = bq + r \]

\[   \Rightarrow b = 51,q = 2,r = 0 \] Here Remainder $r=0$, so, we stop the procedure here and check HCF which is $b = 51$.

Hence by Euclid’s division algorithm, $51$ is the HCF of $867$ and $255$. Hence option (B) is correct.

Note: HCF of two prime numbers is equal to one as a prime number has only two factors, one and the number itself. Always apply the division lemma to the largest number of the two while using Euclid’s division algorithm to calculate HCF. HCF of the two numbers will always be less than equal to the smaller of the numbers of which HCF is being calculated.