Euclid's Division Lemma

• Euclid's Division Lemma:

Given positive integers a and b, there exist unique integers q and r satisfying

a = bq + r, 0  ≤  r < b.

• Difference between Lemma and Algorithm

A  lemma  is a proven statement used for proving another statement.

Where an  algorithm  is a series of well defined steps which gives a procedure for solving a type of problem.

• Q. Use Euclid’s division algorithm to find the HCF of 867 and 255.

Ans. Here 867>255

867 = 255 × 3 + 102

255 = 102 × 2 + 51

102 = 51 × 2 + 0

So, HCF(867, 255) = 51

To write the HCF as a linear combination the following steps to be followed:

51= 255 - 102 × 2

    = 255 - (867 - 255×3)×2

    = 255 - 867×2 + 255×6

    = 255 × 7 - 867 × 2

    = 255 × 7 + 867 × (-2)

    = 867x + 255y

Comparing, we get x = -2, y = 7.

Comment if you have any questions or doubts.