Question

Use the Euclidean division algorithm to find the HCF of $196$ and $38220$.
A) $3$
B) $196$
C) $12$
D) $4$

Answer 1

Hint: We solve this problem by using Euclid’s algorithm. First divide the greater number by the smaller number. If there exists remainder, then divide the smaller number by the remainder. Repeat the process till the number is not exactly divisible.

Formula used: Euclid’s division lemma states that given two positive integers $a$ and $b$, there exists unique integers $q$ and $r$ such that $a = bq + r$.
The integer $q$ is the quotient and the integer $r$ is the remainder.
The numbers $a$ and $b$ are called dividend and divisor respectively.

Complete step-by-step answer:
Given the numbers $196$ and $38220$.
We can see $196 < 38220$
So divide $38220$ by $196$.
Euclid’s division lemma states that given two positive integers $a$ and $b$, there exists unique integers $q$ and $r$ such that $a = bq + r$.
The integer $q$ is the quotient and the integer $r$ is the remainder.
The numbers $a$ and $b$ are called dividend and divisor respectively.
When we divide $38220$ by $196$, we get $195$ as quotient and $0$ as remainder.
We have,
$38220 = 196 \times 195 + 0$
Since the remainder is zero, no further division is possible.
This means the number $196$ is a factor of $38220$. Also $196$ is a factor of itself. No highest factor is possible.
So by Euclid’s division algorithm $196$ itself is the HCF of these two numbers.

Option B is the correct answer.

Note: The Euclidean algorithm division is the simple way to find the highest common factor of two numbers. Another way to find HCF is prime factorisation. Express the given numbers as multiples of powers of prime and find the common factor.