Question

Use Euclid’s division algorithm to find the HCF of: 867 and 255

Answer 1

Hint: Euclid's division algorithm is a technique to compute the highest common factor (HCF) of two given positive integers. HCF of two positive integers a and b is the largest positive integer d that divides both a and b. So, use this concept to reach the solution of the given problem.

Complete step-by-step answer:
Follow the below steps to find the HCF of 867 and 255 by using Euclid's division algorithm
Step 1: First of all, find which integer is larger. Clearly $$867>255$$
Step 2: Then apply the Euclid's division algorithm to 867 and 255 to obtain $$867=255\times 3+102$$
              Repeat the above step until you will get a remainder as zero.
Step 3: Now consider the divisor 255 and the remainder 102, and apply the Euclid`s division
              algorithm to get $$255=102\times 2+51$$
Step 4: Then consider the divisor 102 and the remainder 51, and apply the Euclid's division algorithm
              to get $$102=51\times 2+0$$. Since, the remainder is zero, we cannot proceed further.
Step 5: Hence the divisor at the last process is 51. So, the HCF of 867 and 255 is 51.
Thus, HCF of 867 and 255 is 51.

Note: Highest common factor (HCF) or Greatest common factor (GCD) of two numbers is the largest number that divides both of them. If we have positive integers on dividing both 867 and 255 by 51, then our answer is correct otherwise it is wrong.