Question

Find HCF by Euclid’s division lemma method
(a) 504 and 980
(b) 110089 and 7344
(c) 960 and 1575
(d) 960 and 432

Answer 1

Hint: We solve this problem by first discussing the Euclid’s lemma. Then we apply the lemma on the given numbers Then we apply the lemma on the quotient and the remainder again and again till we get the remainder as zero. Then we take the quotient as the HCF of given two numbers when the remainder is zero. Following this method, we solve all the given subparts.

Complete step by step answer:
First let us discuss the Euclid’s division lemma
For any two positive integers a and b, there exists unique integers q and r which satisfies the condition $a=bq+r$ where $0\le r < b$.
Using this lemma, we can find the HCF between two numbers by using it to write the relation between a and b. Then we take the numbers b and r and apply the Euclid’s lemma again and then use the obtained remainder and the divisor and apply Euclid’s lemma until we get the value of r as zero. Then the last divisor is the HCF of a and b.
Now let us find the HCF of the given numbers.
a) 504 and 980
Using Euclid’s lemma, we can write them as
$980=504\times 1+476$
Now let us take the numbers 504 and 476 and apply Euclid’s lemma
$504=476\times 1+28$
Now, let us take the numbers 476 and 28 and apply Euclid’s lemma
$476=28\times 17+0$
As the remainder is zero, we get that the HCF of 504 and 980 is 28.
Hence, the answer is 28.

b) 110089 and 7344
Using Euclid’s lemma, we can write them as
$110089=7344\times 14+7273$
Now let us take the numbers 7344 and 7273 and apply Euclid’s lemma
$7344=7273\times 1+71$
Now, let us take the numbers 7273 and 71 and apply Euclid’s lemma
$7273=71\times 102+31$
Now, let us take the numbers 71 and 31 and apply Euclid’s lemma
$71=31\times 2+9$
Now, let us take the numbers 31 and 9 and apply Euclid’s lemma
$31=9\times 3+4$
Now, let us take the numbers 9 and 4 and apply Euclid’s lemma
$9=4\times 2+1$
Now, let us take the numbers 4 and 1 and apply Euclid’s lemma
$4=1\times 4+0$
As the remainder is zero, we get that the HCF of 110089 and 7344 is 1.
Hence, the answer is 1.

c) 960 and 1575
Now, let us take the numbers 1575 and 960 and apply Euclid’s lemma
$1575=960\times 1+615$
Now, let us take the numbers 960 and 615 and apply Euclid’s lemma
$960=615\times 1+345$
Now, let us take the numbers 615 and 345 and apply Euclid’s lemma
$615=345\times 1+260$
Now, let us take the numbers 345 and 260 and apply Euclid’s lemma
$345=260\times 1+85$
Now, let us take the numbers 260 and 85 and apply Euclid’s lemma
$260=85\times 3+5$
Now, let us take the numbers 85 and 5 and apply Euclid’s lemma
$85=5\times 17+0$
As the remainder is zero, we get that the HCF of 960 and 1575 is 5.
Hence, the answer is 5.
d) 960 and 432
Now, let us take the numbers 960 and 432 and apply Euclid’s lemma
$960=432\times 2+96$
Now, let us take the numbers 432 and 96 and apply Euclid’s lemma
$432=96\times 4+48$
Now, let us take the numbers 96 and 48 and apply Euclid’s lemma
$96=48\times 2+0$
As the remainder is zero, we get that the HCF of 960 and 432 is 48.
Hence, answer is 48.

Note:
The common mistake one makes while finding HCF of two numbers is they apply the Euclid’s lemma for the numbers till they get the remainder is zero and take the quotient as HCF instead of taking the divisor as HCF.
For example, in the sub-part d,