Question

What is the diffence between Euclid's division lemma and Euclid's division Algorithm? With an example.

Answer 1

By algorithm it means a set of steps to be followed to reach the required answer whereas lemma could be considered as an intermediate step or theorem.
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 ≤ r ≤ b.
whereas consider the example:

Find the HCF of 81 and 675 using the Euclidean division algorithm.

Solution: The larger integer is 675 therefore applying the Division Lemma a = bq + r where 0 ≤ r ≤ b, we have

a = 675 and b = 81

⇒ 675 = 81 × 8 + 27

Applying the Euclid’s Division Algorithm again we have,

81 = 27 × 3 + 0

We cannot proceed further as the remainder becomes zero. According to the algorithm, divisor in this case is 27 which is the HCF of 675 and 81.


The whole steps taken to reach the final answer is an algorithm(collection of steps)