Question

Use Euclid's division lemma to find the HCF :

65 and 495.

• A. $5$
• B. $10$
• C. $15$
• D. $0$

Answer 1

Answer: (A)

$5$

According to Euclid’s Division Lemma if we have two positive integers $a$ and $b$, then there exists unique integers $q$ and $r$ which satisfies the condition $a=bq+r$ where $0\le r<b$.

$HCF$ is the largest number which exactly divides two or more positive integers.

By Euclid's division lemma, we mean that on dividing both the integers $a$ and $b$ , the remainder is zero.

The given integers are $a=65$ and $b=495$.

Clearly $495>65$.

So, we will apply Euclid’s division lemma to $65$ and $495$, we get,

$495=(65\times 7)+40$

Since the remainder $40\ne 0$. So we again apply the division lemma to the divisor $65$ and remainder $40$. We get,

$65=(40\times 1)+25$

Again the remainder $25\ne 0$, so applying the division lemma to the new divisor $40$ and remainder $25$. We get,

$40=(25\times 1)+15$

Now, againthe remainder $15\ne 0$, soapplying the division lemma to the new divisor $25$ and remainder $15$. We get,

$25=(15\times 1)+10$

Againthe remainder $10\ne 0$, soapplying the division lemma to the new divisor $15$ and remainder $10$. We get,

$15=(10\times 1)+5$

Againthe remainder $5\ne 0$, soapplying the division lemma to the new divisor $10$ and remainder $5$. We get,

$10=(5\times 1)+0$

Finally we get the remainder $0$ and the divisor is $5$.

Hence, the $HCF$ of $65$ and $495$ is $5$.