Using Euclid's Algorithm to Find HCF of 196 and 38220

Euclid's algorithm is a method for finding the highest common factor (HCF) of two numbers. It involves dividing the larger number by the smaller number, finding the remainder, and repeating the process until the remainder is zero. The last non-zero remainder is the HCF of the two numbers.

Step 1: Write down the two numbers to be used in the algorithm.

196 and 38220

Step 2: Determine the larger and smaller numbers.

38220 is larger, and 196 is smaller.

Step 3: Divide the larger number by the smaller number.

38220 ÷ 196 = 195 with remainder 150

Step 4: Write the equation using the remainder as the smaller number.

196 ÷ 150 = 1 with remainder 46

Step 5: Repeat the process with the new remainder.

150 ÷ 46 = 3 with remainder 12

Step 6: Repeat the process again.

46 ÷ 12 = 3 with remainder 10

Step 7: Repeat the process again.

12 ÷ 10 = 1 with remainder 2

Step 8: Repeat the process again.

10 ÷ 2 = 5 with remainder 0

Step 9: The HCF is the last non-zero remainder.

The last non-zero remainder is 2, so the HCF of 196 and 38220 is 2.

Note: The process can also be shown using a table.

|Dividend|Divisor|Quotient|Remainder|
|--------|-------|--------|---------|
|38220 |196 |195 |150 |
|196 |150 |1 |46 |
|150 |46 |3 |12 |
|46 |12 |3 |10 |
|12 |10 |1 |2 |
|10 |2 |5 |0 |

Conclusion: Using Euclid's algorithm, the HCF of 196 and 38220 is 2.