Courses
Courses for Kids
Free study material
Offline Centres
More
Store Icon
Store
seo-qna
SearchIcon
banner

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
VerifiedVerified
504.6k+ views
4 likes
like imagedislike image
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 0r<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×1+476
Now let us take the numbers 504 and 476 and apply Euclid’s lemma
504=476×1+28
Now, let us take the numbers 476 and 28 and apply Euclid’s lemma
476=28×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×14+7273
Now let us take the numbers 7344 and 7273 and apply Euclid’s lemma
7344=7273×1+71
Now, let us take the numbers 7273 and 71 and apply Euclid’s lemma
7273=71×102+31
Now, let us take the numbers 71 and 31 and apply Euclid’s lemma
71=31×2+9
Now, let us take the numbers 31 and 9 and apply Euclid’s lemma
31=9×3+4
Now, let us take the numbers 9 and 4 and apply Euclid’s lemma
9=4×2+1
Now, let us take the numbers 4 and 1 and apply Euclid’s lemma
4=1×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×1+615
Now, let us take the numbers 960 and 615 and apply Euclid’s lemma
960=615×1+345
Now, let us take the numbers 615 and 345 and apply Euclid’s lemma
615=345×1+260
Now, let us take the numbers 345 and 260 and apply Euclid’s lemma
345=260×1+85
Now, let us take the numbers 260 and 85 and apply Euclid’s lemma
260=85×3+5
Now, let us take the numbers 85 and 5 and apply Euclid’s lemma
85=5×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×2+96
Now, let us take the numbers 432 and 96 and apply Euclid’s lemma
432=96×4+48
Now, let us take the numbers 96 and 48 and apply Euclid’s lemma
96=48×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,