What is Euclid's Division or Lemma, Real Number, Part-1

So far we provide knowledge about rational number, irrational numbers, Linear Equation, now, we shall study Real number, its feature and its usages along with details solved problem.

What is Euclid’s Division?

 Euclid’s Division Lemma or Euclid’s division algorithm: For any two given positive integers a and b there exist unique whole numbers q and r such that

 a = bq + r, where 0 > r > b.

Here, we call a as dividend, b as divisor, q as quotient and r as remainder.

Dividend = (divisor x quotient) + remainder.

 

Example : – Suppose we divide 117 by 14, then w get,

 i

    14 )  117 (8

-                  112   

     xx5

        8 as quotient and 5 as remainder. Here dividend = 117, divisor =14, quotient = 8

Problem 1. A number when divided by 53 gives 34 as quotient and 231 as remainder. Find the number.

Solution:- By Euclid’s division algorithm, we have:

Dividend = (divisor x quotient ) + remainder

              = ( 53 x 34  ) + 21

              = (1802 + 21 ) = 1823

Hence, the required number is 1823

Problem 2. Show that every positive even integer is of the form 2q and that every positive odd integer is of the form 2q + 1 for some integer q.

Solution:- Let us suppose that a be a given positive integer.

On dividing a by 2, let q be the quotient and r be the remainder.

Then, by Euclid’s algorithm, we have,

               a = 2q + r, whter 0 < r<2

ð                                      a = 2q + r, where r =0 or r = 1

ð                                      a = 2q or a = 2q + 1.

When a = 2q for some integer q, then clearly a is ever.

Also, an integer can be either even or odd.

Hence, an odd integer is of the form  2q + 1 for some integer q. thus, every positive even integer is of the form 2q and every positive odd integer is fo the form 2q + 1 for some integer q. Proved

Problem3. Show that every positive odd integer is of the form (4q + 1) or (4q + 3).

Proof:- We know that an odd positive n is of the form (4q + 10 or (4q + 3 ) for some integer q.

Case 1. When n = (4q +1).

In this case, we have,

(n² - 1 ) = (4q + 1 ) = ( 16 q² + 8q ) = 8q ( 2q + 1 ),

Which is clearly divisible by 8.

Case II. When n + (4q + 3 ),

In this case, we have,

(n² - 1 ) = ( 4q + 3 )² - 1 = 16q² + 24q + 9 – 1 = 16q² + 24q + 8

             = 8 (2q² + 3q + 1), which is divisible by 8.

Hence, (n² +1 ) is divisible by 8.

                                                   Proved

Problem5. Show that every positive odd integer is of the form (6q +1 ) or ( 6q + 3 ) or (6q + 5 )for some integer q.

Proof: Let us suppose that a be a given positive odd integer.

On dividing a by 6, let q be the quotient and r be the remainder.

Then, by Euclide’s algorithm, we have:-

               a = 6q + r, where 0 < r <6

ð  a = 6q + r, where r = 0,1,2,3,4,5

ð  a = 6q or a = 6q + 2 or a = 6q + 3

ð  or a = 6q + 4,  or a = 6q +5,

But, a = 6q, a = 6q + 2, a = 6q +4 give even values of a.

Thus, when a is odd, it is in the form of 6q + 1 or 6q + 3, or 6q + 5 for some integer q. Proved

Problem 6:- Show that every positive even integer is of the form 2q and that every positive odd integer is of the form ( 2q + 1 ) for some positive integer q.

Proof: Let us suppose that n be an arbitrary positive integer. On dividing n by 2, let q be the quotient and r be the remainder.

Then, by Euclid’s algorithm, we have,

n = 2q + r, where 0 < r<2

ð        n = 2q or n = 2q + 1.

Case I. When n = 2q,

In this case, n is clearly even. 

Case II. When n = 2q +1

In this case, n is clearly odd.

Therefore, every even integer is of the form 2q  and every odd integer is of the form (2q + 1)

Problem 7:- Show that one and only one out of n, (n + 1) and (n + 2 ) is divisible by 3, where n  is any positive integer.

Proof:- On dividing n by 3, let q be the quotient and r be remainder.

Then,     n = 3q + r, where 0 < r <3

ð  n = 3q + r,  where r = 0, 1 or 2

ð  n = 3q or n = ( 3q + 1 ) or n = ( 3q + 2 ).

Case I. If n = 3q, then n is clearly divisible by 3.

Case II. If n = ( 3q + 1 ), then ( n + 2 ) = ( 3q + 2 ) = (3q + 3 ) = 3 ( q + 1 ), which is clearly divisible by 3. 

Case III. If n = (3q + 2 ), then  ( n + 1 ) = ( 3q + 3 ) = 3 ( q + 1 ), which is clearly divisible by 3.

Hence, one and only one out of n, ( n + 1 ) and ( n + 2 ) is divisible by 3.

Problem 8:- Show that one and only one out of n, n + 2, n + 4 is divisible by 3, when n is any positive interger.

Then, n = 3q + r, where 0 < r < 3

ð  n = 3q + r, where r = 0, 1, 2

ð  n = 3q or n = 3q + 1  or n = 3q + 2

Case I :- if n = 3q, then n is divisible by 3. 

Case II :- if n = 3q + 1, then (n + 2) = 3q +3 = 3 (q +1), which is divisible by 3.

So in this case, ( n +2) is divisible by 3

Hence, one and only one out of n, ( n + 2 ), ( n + 4 ) is divisible by 3.

Problem 9. Use Euclid’s Division Lemma to show that the square of any positive integer is either of the form 3m or 3m + 1 for some integer m.

Proof:- Let us suppose that a be an arbitrary positive integer. Then, by Euclid’s Division Algorithm, corresponding to the positive integers a and 3, there exist non-negative integers q and r such that 

a = 3q +r, whre 0 < r<3

ð  a² = 9q² + r² + 6qr    …………………….(1) where 0 < r < 3

Case I:- When r = 0

Putting r = 0 in (i), we get,

ð  a² = 9q² + r² +6qr

ð  a² = 9q² + 0² + 6q0 = 9q² = 3 (3q²) = 3m, where m = 3q² is an integer.

Case II:- When r = 1

Putting r = 1 in euqⁿ (i), we get,

a² = 9q² + 12 + 6q1 = 9q² + 1 + 6q = 3(3q² + 2q) + 1 = 3m +1,

CaseIII:- When r = 2

Putting value of r into equation (1), we get,

a² = (3q)² + r² + 6qr = 9q² +2² + 12q² = 9q² + 4 +12q = (9q² + 12q) + 4

=( 9q² + 12q + 4 ) = 3q (3q + 4q + 4 ) + 1 = 3m + 1,

Where m = (3q +4q + 1 ) is an integer.

Hence, the square of any positive integer is either of the form 3m or 3m + 1 for some integer m.   

PROBLEM 10:- Using Euclid’s Division Lemma, show that the cube of nay positive integer is of the form 9q or (9q + 1 ) or (9q + 8 ) for some integer q.

Proof:- let us suppose that a be an arbitrary positive integer.

Then, by Euclid’s Division Algorithm, corresponding to the positive integers a and 3, there exist non-negative integers m and r such that

a = 3m + r, where 0 < r < m

ð  a³ = (3m + r )³ = 27 m³ + r³ + 9mr (3m + r )

ð  a³ = ( 27m³ + 27m²r + 9mr² )³ + r³    ………………………………(i),

where 0 < r < m

Now, Case I:- When r = 0

Putting the value of r in equation ( i), we get,

a³ = 27 m³  = 9 ( 3m³)

ð  a³ = 9q, where q = qm3 is an integer.

Case II:- When r = 1

Putting value of r in equation (i), we get,

a³= ( 27q³ + 27m² + 9m) + 1

= 9m ( 3m² + 3m + 1 ) + 1

= 9m ( 3m² + 3m + 1 ) + 1

= ( 9q + 1 ), where q = m (3m² + 3 m + 1 ) is an interger.

Case III:- When r = 2

Putting the value of r in equation (i), we get,

a³ = ( 27m³ + 54m² + 36m ) + 8

= 9m ( 3m² + 54m² + 36m) + 8

= 9m ( 3m² + 6m + 4 ) + 8

= ( 9q + 8 ), where q = m (3m² + 6m + 4 ) is an interger.

Hence, the cube of any positive integer is of the form 9q or (9q +1 ) or ( 9q + 8 ) for some integer.   

Continue………………………..