EUCLID'S DIVISION LEMMA

Euclid, one of the most important mathematicians wrote an important book named 'Elements' in 13 volumes. The first six volumes were devoted to Geometry and for this
reason, Euclid is called the 'Father of Geometry'. But in the next few volumes, he made fundamental contributions to understand the properties of numbers. One among them is the 'Euclid’s Division Lemma'. This is a simplified version of the long division process that you were performing for division of numbers in earlier classes.

Le us now discuss Euclid’s Lemma and its application through an Algorithm termed as 'Euclid’s Division Algorithm'.

Theorem : Euclid’s Division Lemma

Note : 

1. The above lemma is nothing but a restatement of the long division process, the integers q and r are called quotient and remainder respectively.

2. When a positive integer is divided by 2 the remainder is either 0 or 1. So, any positive integer will of the form 2k, 2k+1 for some integer k.

Generalized form of Euclid’s division lemma

Example 1 :

We have 34 candies. Each box can hold 5 candies only. How many boxes we need to pack and how many candies are unpacked?

Solution :

We see that 6 boxes are required to pack 30 candies with 4 cakes left over. This distribution of candies can be understood as follows :

Dividend a ---->  Total number of candies

Divisor b ----> Number of candies in each box

Quotient q ----> Number of boxes

Remainder r ----> Number of candies left over

Example 2 :

Find the quotient and remainder when a is divided by b in the following cases

(i) a = -12, b = 5

(ii) a = 17, b = -3

(iii) a = -19, b = -4

Solution :

(i) a = -12 , b = 5

By Euclid’s division lemma

 a = bq + r , where 0 ≤ < r < |b|

-12 = 5(-3) + 3, 0 ≤ < r < |5|

Therefore, Quotient q = -3, Remainder r = 3.

(ii) a = 17 , b = -3

By Euclid’s division lemma

 a = bq + r , where 0 ≤ < r < |b|

17 = -3(-5) + 2, 0 ≤ < r < |-3|

Therefore, Quotient q = -5, Remainder r = 2.

(iii) a = -19 , b = -4

By Euclid’s division lemma

 a = bq + r , where 0 ≤ < r < |b|

-19 = -4(5) + 1, 0 ≤ < r < |-4|

Therefore, Quotient q = 5, Remainder r = 1.

Example 3 :

For some integer q, show that the square of an odd integer is of the form 4q + 1. 

Solution :

Let x be any odd integer. Since any odd integer is one more than an even integer, we have x = 2k + 1, for some integer k.

x² = (2k + 1)²

= (2k)² + 2(2k)(1) + 1²

= 4k² + 4k + 1

= 4k(k + 1)

= 4q + 1

where q = k(k + 1) is some integer.

Kindly mail your feedback to v4formath@gmail.com

We always appreciate your feedback.