Question

Using Euclid's Division lemma, find the HCF of 867 and 255.

Answer 1

Hint: Finding HCF using Euclid's division lemma is an algorithmic process. We start by setting the two variables p and q equal to the given numbers, with q being equal to the smaller one. Then we repeat the following process:

Complete step-by-step answer:
Apply Euclid's division lemma to the numbers p and q
i.e. p = aq+r where $0\le r\le q-1$
if r = 0 then stop the process and we have HCF = q
Otherwise set p = q and q =r and repeat the process.
We set p =867 and q = 255.
Now we apply Euclid's division lemma on p and q, we get
$867=255\times 3+102$
Here r = 102.
So we set p = 255 and q =102 and repeat the process
Applying Euclid's division lemma on p and q, we get
$255=102\times 2+51$
Here r = 51.
So we set p = 102 and q =51 and repeat the process
Applying Euclid's division lemma on p and q, we get
$102=51\times 2+0$
Since r = 0, we stop the process and we have HCF = q =51.
Hence by Euclid's division algorithm HCF (867,255)=51.

Note: Verification:
If g is the HCF of a and b then g must divide both a and b and the quotients obtained on dividing a by g and b by g should be coprime.
We have $867=51\times 17$ and $255=51\times 5$
Hence 51 divides 867 and 255.
Also 17 and 5 are distinct primes and hence are coprime to each other.
Hence 51 is the HCF of 867 and 255.
Hence the answer is verified to be correct.