Use Euclid's division algorithm to find the H.C.F. of 867 and 255

Answer

To find the H.C.F. (Highest Common Factor) of 867 and 255 using Euclid's Division Algorithm, we will follow these steps:

### Step 1: Apply Euclid's Division Algorithm
We start by dividing the larger number (867) by the smaller number (255).

\[ 867 = 255 \times Q + R \]

Where:
- \( Q \) is the quotient
- \( R \) is the remainder

### Step 2: Calculate the Quotient and Remainder
Now, we perform the division:

1. Divide 867 by 255.
2. The quotient \( Q \) is 3 (since \( 255 \times 3 = 765 \)).
3. The remainder \( R \) is calculated as follows:

\[ R = 867 - 765 = 102 \]

So, we can write:

\[ 867 = 255 \times 3 + 102 \]

### Step 3: Repeat the Process
Next, we apply the same algorithm to the divisor (255) and the remainder (102):

\[ 255 = 102 \times Q + R \]

### Step 4: Calculate the New Quotient and Remainder
1. Divide 255 by 102.
2. The quotient \( Q \) is 2 (since \( 102 \times 2 = 204 \)).
3. The remainder \( R \) is:

\[ R = 255 - 204 = 51 \]

So, we can write:

\[ 255 = 102 \times 2 + 51 \]

### Step 5: Continue the Process
Now, we repeat the process with 102 and 51:

\[ 102 = 51 \times Q + R \]

### Step 6: Calculate the Quotient and Remainder
1. Divide 102 by 51.
2. The quotient \( Q \) is 2 (since \( 51 \times 2 = 102 \)).
3. The remainder \( R \) is:

\[ R = 102 - 102 = 0 \]

So, we can write:

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

### Step 7: Conclusion
Since the remainder is now 0, we stop here. The last non-zero remainder is 51, which is the H.C.F. of 867 and 255.

Thus, the H.C.F. of 867 and 255 is:

\[ \text{H.C.F.} = 51 \]

---