what is the difference between Euclid's division algorithm and Euclid's division lemma.explain with example.
Share
what is the difference between Euclid's division algorithm and Euclid's division lemma.explain with example.
Sign Up to our social questions and Answers Engine to ask questions, answer people’s questions, and connect with other people.
Login to our social questions & Answers Engine to ask questions answer people’s questions & connect with other people.
Euclid's division lemma: For given any positive integers a and b there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b.
Euclid's division algorithm is used for finding the Highest Common Factor of two numbers where in we apply the statement of Euclid's division lemma.
For any two positive integers a and b, there exist unique integers q and r satisfying a = bq + r, where 0 ≤ r < b.
For Example
(i) Consider number 23 and 5, then:
23 = 5 × 4 + 3
Comparing with a = bq + r; we get:
a = 23, b = 5, q = 4, r = 3
and 0 ≤ r < b (as 0 ≤ 3 < 5).
Euclids division algorithm. : a method of finding the greatest common divisor of two numbers bydividing the larger by the smaller, the smaller by the remainder, the first remainder by the second remainder, and so on until exact division is obtained whence the greatest common divisor is the exact divisor.
Examples :
1) Use Euclid’s algorithm to find the 420 and 130.
Solution :
Step:1 Since 420 > 130 we apply the division lemma to 420 and 130 to get ,
420 = 130 x 3 + 30
Step:2 Since 30 ≠ 0 , we apply the division lemma to 130 and 30 to get
130 = 30 x 4 + 10
Step:3 Since 10 ≠ 0 , we apply the division lemma to 30 and 10 to get
30 = 10 x 3 + 0
The remainder has now become zero, so our procedure stops. Since the divisor at this Step is 10, the HCF of 420 and 130 is 10.
Hope it will hlp u..plz mark as bainliest answer!!