Question

Use Euclid’s division algorithm to find the HCF of the following numbers: $55$ and $210$.

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. HCF will be the last non zero remainder.

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 $55$ and $210$.
We can see $55 < 210$
So divide $210$ by $55$.
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 $210$ by $55$, we get $3$ as quotient and $45$ as remainder.
So we can write $210 = 55 \times 3 + 45$
Then again divide $55$ using the remainder $45$.
We get $1$ as a quotient and $10$ as remainder.
So we can write $55 = 45 \times 1 + 10$
Since we get a non zero remainder, we again apply division lemma.
Dividing $45$ by the new remainder $10$ we get,
$45 = 10 \times 4 + 5$
Again we got non zero remainder $5$.
Dividing by $10$ by $5$ we get,
$10 = 5 \times 2 + 0$
Thus we get a zero remainder. So no further division is possible.
So the HCF is the last non zero remainder which is equal to $5$.
$\therefore $ The answer is $5$.

The HCF of 55 and 210 is 5.

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 factors.