Question

The HCF of 196 and 38416 using Euclid algorithm is
A) 191
B) 192
C) 193
D) 196

Answer 1

Hint: An Euclid algorithm is the technique of calculating the highest common factor or greatest common divisor of two given positive numbers by dividing the larger number by the smaller, the smaller by the remainder and the first remainder by the second remainder and till exact division is obtained.

Complete step-by-step solution
To obtain the HCF of two positive integers, say c and d, with \[c > d\], follow the steps below:
Apply Euclid’s division lemma, to c and d. So, we find whole numbers, q and r such that \[c = dq + r,0 \leqslant r < d\] If r=0, d is the HCF of c and d. If r​=0, apply the division lemma to d and r. Continue the process until the remainder is zero. The divisor at this stage will be the required HCF.
Let us apply Euclid’s division algorithm to the given numbers 196 and 38416 as follows:
\[38416 = 196 \times 196 + 0\]
 As, in the first attempt only, the remainder comes zero so, the HCF of 196 and 38416 is 196.

Hence option D is the correct answer.

Note: Alternatively, the HCF between the numbers can be determined by multiplying all the common factors of the numbers involved in the calculation.
Factoring the number 196 as: $196 = 2 \times 2 \times 7 \times 7 - - - (i)$
Similarly, factoring the number 38416 as: $38416 = 2 \times 2 \times 2 \times 2 \times 7 \times 7 \times 7 \times 7 - - - - (ii)$
Taking all the highest common factors and multiplying them to get the HCF as $2 \times 2 \times 7 \times 7 = 196$.