Lemma is an auxiliary result used for proving an important theorem. It is usually considered as a mini theorem.

**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 Divison 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”.

Lemma is an auxiliary
result used for proving an important theorem. It is usually considered as a
mini theorem.

Let *a *and *b *(*a
*> *b*) be any two positive integers. Then, there exist unique
integers *q* and *r *such that *a *= *bq *+ *r*, 0 ≤ *r
*< *b.*

**Note**

·
*The remainder is always less than the divisor.*

·
*If r = 0 then a =
bq so b divides a. *

·
*Similarly, if b divides a then a = bq*

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

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

**NOTE**

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

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

Euclid’s Division
Lemma can be generalised to any two integers.

If *a *and *b *are
any two integers then there exist unique integers *q *and *r *such
that* a *= *bq *+*r *, where 0 ≤|*r| *< |b|

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

(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 .

Show that the square
of an odd integer is of the form 4*q *+ 1 , for some integer *q*.

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

*x*^{2} = (2*k *+ 1)^{2}

= 4*k*^{2}
+ 4*k *+ 1

= 4*k*(*k *+
1) + 1

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

Tags : Theorem, Example, Solution Theorem, Example, Solution

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.