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