Use Euclid's algorithm to find `HCF ( 196 , 38220) `.

Options

A. 98
B. 196
C. 49
D. none of these

Explanation

To find the HCF (Highest Common Factor) of 196 and 38220 using Euclid's algorithm, we will follow these steps:

### Step 1: Identify the numbers
We have two numbers:
- a = 38220 (the larger number)
- b = 196 (the smaller number)

### Step 2: Apply Euclid's Division Algorithm
According to Euclid's algorithm, we can express a as:
\[ a = b \cdot q + r \]
where:
- \( a \) is the dividend (38220)
- \( b \) is the divisor (196)
- \( q \) is the quotient
- \( r \) is the remainder

### Step 3: Perform the division
Now, we divide 38220 by 196:
1. Calculate the quotient \( q \):
\[ q = \left\lfloor \frac{38220}{196} \right\rfloor = 195 \]
2. Calculate the remainder \( r \):
\[ r = 38220 - (196 \cdot 195) \]
\[ r = 38220 - 38220 = 0 \]

### Step 4: Check the remainder
Since the remainder \( r \) is 0, we can conclude that the HCF is the divisor from this step.

### Step 5: Conclusion
Thus, the HCF of 196 and 38220 is:
\[ \text{HCF} = 196 \]

### Summary of Steps:
1. Identify the larger and smaller numbers.
2. Apply Euclid's division algorithm to find the quotient and remainder.
3. Check the remainder; if it is 0, the HCF is the divisor.