# 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

• 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

Home Page