Euclid’s Division Lemma

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

The word algorithm comes from the name of the 9th century Persian mathematician al-Khwarizmi. In fact, even the word ‘algebra’ is derived from a book, he wrote, called Hisab al-jabr w’al-muqabala.

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

Euclid's division lemma, as the name suggests, its related to the divisibility of four integers or it's based on division. To understand this division lemma let's look at a real-life example. Let's assume that there are seven pens, take three pens at a time and put it in two boxes. Now there will three pens in each box and one pen will be left out.

Now using basic division we can write it as `7/3`=2 with a remainder of 1. Here, 7 is the dividend, 3 is the divisor, 2 is the quotient and 1 is the remainder.

There is one more way to write this, that is, `7= 3 xx 2 + 1`

We can represent the same equation using variables, let's take 7 as 'a', 3 as 'b', 2 as 'q' and 1 as 'r'. So now it will look like `a = b xx q + r`. This is same as Dividend = divisor × quotient+ remainder. This generalized using variables is called Euclid's division lemma which is nothing but will be like this given positive integers 'a' and 'b', there exists unique integers 'q' and 'r' satisfying a = bq+r, where 0 ≤ r < b, that the remainder 'r' can be 0 but less than the divisor 'b'.

Now going back to the example, the number of pens is 7 which is fixed and 3 pens per box that's also fixed then it is obvious that the number of boxes which you can take and the left out pens they are getting fixed by default that is why the word unique integers is used in this explanation because as there will be only one set of solution.

Let us see the application of Euclid's division lemma. Show that every odd positive integer is of form 4q+1 or 4q+3 where q is some integer. As per Euclid's division lemma a=bq+ r. When compared with the given example, b=4 and 0 ≤ r < 4.

By applying the lemma we get the possible value of 'a' as

a=(4q) or (4q+1) or (4q+2) or (4q+3). As per asked in the example odd positive integer is (4q+1) and (4q+3)

Another use of Euclid's division lemma is to find HCF ( Highest Common Factors)

Let's assume two numbers that are 32 and 18. The first step will be 32= 18 × 1 + 14  We will continue this step till we get remainder as 0.

Next 18 will become the dividend and 14 will be the divisor, 18 = 14 × 1 + 4

Similarly, 14 will be dividend and 4 will be the divisor, 14 = 4 × 3 + 2 

4 will become dividend and 2 will become divisor, 4 = 2 × 2 + 0

Once we get remainder as 0 the divisor that is 2 here will be the HCF. This Euclid's division lemma using numbers.