Question

Use Euclid's algorithm to find the HCF of 2322 and 654​

Answer 1

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

2,322 ÷ 654 = 3 + 360;

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

654 ÷ 360 = 1 + 294;

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

360 ÷ 294 = 1 + 66;

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

294 ÷ 66 = 4 + 30;

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

66 ÷ 30 = 2 + 6;

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

30 ÷ 6 = 5 + 0;

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

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

This is the greatest common factor (divisor).