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.

a = bq + r, 0 ≤ r ≤ b.

If b | a, then r=0. Otherwise, ‘r’ satisfies the stronger inequality 0 ≤ r ≤ b.

…, 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.

1) Show that n

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 :

In this case, we have

n

= 16q

= 8q ( 2q + 1)

⇒ n

In this case, we have

n

= 16q

= 16q

⇒ n

⇒ n

Hence, n

--------------------------------------------------------------------

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.

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

GMAT

GRE

1st Grade

2nd Grade

3rd Grade

4th Grade

5th Grade

6th Grade

7th grade math

8th grade math

9th grade math

10th grade math

11th grade math

12th grade math

Precalculus

Worksheets

Chapter wise Test

MCQ's

Math Dictionary

Graph Dictionary

Multiplicative tables

Math Teasers

NTSE

Chinese Numbers

CBSE Sample Papers