Question

Use Euclid’s division lemma to find the HCF: $65$ and $495$ .

Answer 1

Hint: Here we have to find the Highest common factor or HCF of two numbers by using Euclid’s division lemma. So, we will use the step-by-step method of Euclid’s division algorithm. Hence, we will find the largest number which will exactly be dividing the two numbers which are the HCF of two numbers.

Complete step-by-step answer:
We should know that the largest positive integer which will divide the two or more integers without any remainder is called the Highest Common factor or Greatest Common Factor or Divisor.
As we know that according to Euclid’s division lemma if we have two positive integers $a$ and $b$ , then there exist unique integers $q$ and $r$ which satisfies the condition $a = bq + r$ , where $0 \leqslant r < b$ .
So, we can conclude by Euclid’s division lemma that on dividing both the integers, the remainder is zero i.e., $0$ .
In the question we have
 $a = 65,b = 495$ .
 So we can clearly see that
$b > a(495 > 65)$ .
By applying Euclid’s division lemma we can write this as:
$495 = (65 \times 7) + 40$ .
Here we can say that we have remainder $40$ , which is not equal to zero i.e., $40 \ne 0$ .
So, we will again apply the division lemma to the divisor $65$ and $40$ , we can write:
$65 = (40 \times 1) + 25$
Again, we can see that the remainder is $25 \ne 0$ . So, we will again apply the division lemma to the new divisor $40$ and remainder $25$ . We get:
$40 = (25 \times 1) + 15$
We can see that the remainder is $15 \ne 0$ . So, we will again apply the division lemma to the new divisor $25$ and remainder $15$ . We get:
$25 = (15 \times 1) + 10$
Again, we can see that the remainder is $10 \ne 0$ . So, we will again apply the division lemma to the new divisor $15$ and remainder $10$ . We get:
$15 = (10 \times 1) + 5$
Here is the remainder: $5 \ne 0$ . So, we will again apply the division lemma to the new divisor $10$ and remainder $5$ . We get:
$10 = (5 \times 1) + 0$
So finally, we get the remainder zero and the divisor is $5$
Hence the HCF of $65$ and $495$ is $5$ .

Note: We should note that the HCF of two numbers will always be less than or equal to the smaller of the numbers of which HCF is being calculated. In this way we can also cross-check our answers. We should also know that the HCF of two prime numbers is always equal to one as a prime number has only two factors, $1$ and the number itself.