Question

Find the hcf of 143 and 227 by euclid's method

Answer 1

Step 1. Divide the larger number by the smaller one:

227 ÷ 143 = 1 + 84;

Step 2. Divide the smaller number by the above operation's remainder:

143 ÷ 84 = 1 + 59;

Step 3. Divide the remainder from the step 1 by the remainder from the step 2:

84 ÷ 59 = 1 + 25;

Step 4. Divide the remainder from the step 2 by the remainder from the step 3:

59 ÷ 25 = 2 + 9;

Step 5. Divide the remainder from the step 3 by the remainder from the step 4:

25 ÷ 9 = 2 + 7;

Step 6. Divide the remainder from the step 4 by the remainder from the step 5:

9 ÷ 7 = 1 + 2;

Step 7. Divide the remainder from the step 5 by the remainder from the step 6:

7 ÷ 2 = 3 + 1;

Step 8. Divide the remainder from the step 6 by the remainder from the step 7:

2 ÷ 1 = 2 + 0;

At this step, the remainder is zero, so we stop:

1 is the number we were looking for, the last remainder that is not zero.

This is the greatest common factor (divisor).

Greatest (highest) common factor (divisor):

gcf, gcd (143; 227) = 1