Euclids Division Lemma

In this section we will discuss Euclids division lemma a new way of thinking the study of geometry.

Euclid was the first Greek Mathematician who initiated a new way of thinking the study of geometry.
A Euclids division lemma is a proven statement which is used to prove other statements.
Consider the division of positive integer by positive integer, say 58 by 9.

Here, 9 is the divisor, 58 is the dividend, 6 is the quotient and 4 is the remainder.
We can write the result in following form
Dividend = Divisor X quotient + Remainder
58 = 9 x 6 + 4; 0 ≤ 4 ≤ 9
For each pair of positive integers a and b, we can find unique integers q and r satisfying the relation
a = bq + r , 0 ≤ r ≤ b.
In fact, this holds for every pair of positive integers as proved in the following lemma.

Euclids division lemma : Let ‘a’ and ‘b’ be any two positive integers. Then there exist unique integers ‘q’ and ‘r’ such that
a = bq + r, 0 ≤ r ≤ b.
If b | a, then r=0. Otherwise, ‘r’ satisfies the stronger inequality 0 ≤ r ≤ b.
Proof : Consider the following arithmetic progression
…, a – 3b, a – 2b, a – b, a, a + b, a + 2b, a + 3b, …
Clearly, it is an arithmetic progression with common difference ‘b’ and it extends infinitely in both the directions.
Let ‘r’ be the smallest non-negative term of this arithmetic progression. Then, there exists a non-negative integer ‘q’ such that,
a – bq = r ⇒ a = bq + r
As, r is the smallest non-negative integer satisfying the above result. Therefore, 0 ≤ r ≤ b
Thus, we have
a = bq1 + r1 , 0 ≤ r1 ≤ b
We shall now prove that r1 = r and q1 = q
We have,
a = bq + r and a = bq1 + r1
⇒ bq + r = bq1 + r1
⇒ r1 – r = bq1 – bq
⇒ r1 – r = b(q1 – q)
⇒ b | r1 – r
⇒ r1 – r = 0 [ since 0 ≤ r ≤ b and 0 ≤ r1 ≤ b ⇒ 0 ≤ r1 - r ≤ b ]
⇒ r1 = r
Now, r1 = r
⇒ -r1 = r
⇒ a – r1 = a – r
⇒ bq1 = bq
⇒ q1 = q Hence, the representation a = bq + r, 0≤ r ≤ b is unique.

Examples Euclids division lemma
1) Show that n
2 - 1 is divisible by 8, if n is an odd positive integer.
Solution :
We know that any odd positive integer is of the form 4q + 1 or 4q + 3 for some integer q.
So, we have the following cases :
Case I When n = 4q + 1
In this case, we have
n
2 - 1 = (4q + 1) 2 - 1 = 16q 2 + 8q + 1 – 1
= 16q
2 + 8q
= 8q ( 2q + 1)
⇒ n
2 - 1 is divisible by 8 [ since 8q ( 2q + 1) is divisible by 8]
Case II When n = 4q + 3
In this case, we have
n
2 -1 = (4q + 3) 2 - 1
= 16q
2 + 24q + 9 – 1
= 16q
2 + 24q + 8
⇒ n
2 - 1 = 8(2q 2 + 3 q + 1)
⇒ n
2 - 1 is divisible by 8 [ since 8(2q 2 + 3 q + 1) is divisible by 8]
Hence, n
2 - 1 is divisible by 8.
--------------------------------------------------------------------
2) Show that every positive even integer is of the form 2q, and that every positive odd integer is of the form 2q + 1, where q is some integer.
Solution :
Let ‘a’ be any positive integer and b = 2. Then, by Euclid’s division Lemma there exists integers q and r such that
a = 2q + r , where 0 ≤ r < 2
Now, 0 ≤ r < 2 ⇒ 0 ≤ r ≤ 1 ⇒ r = 0 or r = 1 [ since r is and integer]
∴ a = 2q or a = 2q + 1
If a = 2q, then ‘a’ is an even integer.
We know that an integer can be either even or odd. Therefore, any odd integer is of the form of 2q + 1.

Euclid's Geometry

Euclid Geometry
Euclids division lemma
Euclids division Algorithm
Fundamental Theorem of Arithmetic
Finding HCF LCM of positive integers
Proving Irrationality of Numbers
Decimal expansion of Rational numbers

From Euclids division lemma to Real numbers

Home Page