Find the HCF of 865 and 255 by Euclid Division Algorithm
Answers
Answer:HCF OF 255 ND 865
865>255
865=255×3+100
255=100×2+55
100=55×1+45
55=45×1+10
45=10×4+5
10=5×2+0
HCF=5
Given: Two numbers- 865 and 255
To find: HCF of given numbers using Euclid's Division Lemma
Solution:
(Definition - According to Euclid's division lemma, if we have two positive integers a and b, then there exist unique integers q an r which satisfies the condition a = bq + r where 0 ≤ r < b)
The greater integer is 865 and smaller is 255
We need to apply Euclid's Division Lemma (a = bq + r) on the given numbers, where a = 865 and b = 255.
We get,
⇒ 865 = 255 × 3 + 100
Now, we need to apply Euclid's Division Lemma again taking a = 255 and b = 100
⇒ 255 = 100 × 2 + 55
Taking a = 100 and b = 55
⇒ 100 = 55 × 1 + 45
Taking a = 55 and b = 45
⇒ 55 = 45 × 1 + 10
Taking a = 45 and b = 10
⇒ 45 = 10 × 4 + 5
Taking a = 10 and b = 5
⇒ 10 = 5 × 2 + 0
As the remainder has become 0, we can't proceed further.
Now, the divisor is 5 when remainder is 0.
Hence, 5 is the HCF of 865 and 255.