Euclids Division Lemma

We at ask-math believe that educational material should be free for everyone. Please use the content of this website for in-depth understanding of the concepts. Additionally, we have created and posted videos on our youtube.

We also offer One to One / Group Tutoring sessions / Homework help for Mathematics from Grade 4th to 12th for algebra, geometry, trigonometry, pre-calculus, and calculus for US, UK, Europe, South east Asia and UAE students.

Affiliations with Schools & Educational institutions are also welcome.

Please reach out to us on [email protected] / Whatsapp +919998367796 / Skype id: anitagovilkar.abhijit

We will be happy to post videos as per your requirements also. Do write to us.

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 n2 - 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
n2 - 1 = (4q + 1)2 - 1 = 16q2 + 8q + 1 – 1
= 16q2 + 8q
= 8q ( 2q + 1)
⇒ n2 - 1 is divisible by 8 [ since 8q ( 2q + 1) is divisible by 8]
Case II When n = 4q + 3
In this case, we have
n2-1 = (4q + 3)2 - 1
= 16q2 + 24q + 9 – 1
= 16q2 + 24q + 8
⇒ n2 - 1 = 8(2q2 + 3 q + 1)
⇒ n2 - 1 is divisible by 8 [ since 8(2q2 + 3 q + 1) is divisible by 8]
Hence, n2 - 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

Russia-Ukraine crisis update - 3rd Mar 2022

The UN General assembly voted at an emergency session to demand an immediate halt to Moscow's attack on Ukraine and withdrawal of Russian troops.