Euclid's Division Lemma

Euclid's Division Lemma

Divisibility: There are three states in digital

(i) when a non zero integer 'a' is divide bye an integer 'b'. if there exist an integer 'q' such that 

a = b q.

     ___

b)  a    (q

     a   

      0

Here integer a is dividend and integer b is divisor and q is quotient.

now we are taking an example

     ___

8)   59    (7

       56   

          3

     ___

a)   b    (q

       b   

       r

a = b q + r

0 ≤ r < b

Type (1)

Q.1 Show that every positive even integer is of the form 2q.

Sol.

Let a be any positive integer and 

b = 2. 

Now by euclid's division lemma

a = b q + r. or a = 2 q + r

where 0 ≤ r < 2.       (0, 1)

(i) if r = 0

a = 2 q + 0

hanc a = 2 q is some even integer.

(ii) if r = 1

a = 2 q + 1

hanc a = 2 q + 1 is some odd integer.

Type (2)

Q.1 Show that every positive even integer is of the form 2q, and that every positive odd integer is of the form to 2q + 1 where q is some integer.

Sol.

Let a be any positive integer and 

b = 2. 

Now by euclid's division lemma

a = b q + r. or a = 2 q + r

where 0 ≤ r < 2

(i) if r = 0

a = 2 q + 0

2q is divisible by 2 so that it is an even number.

(ii) if r = 1

a = 2 q + 1

2q is divisible by 2 but 1 is not, so that it is an odd number. 

(iii) if r = 2

a = 2 q + 2

2q is divisible by 2 and 2 is also, so that it is an even number.

(iv)  if r = 3

a = 2 q + 3

2q is divisible by 2 but 3 is not, so that it is an odd number. 

Q.2 Show that every positive even integer is of the form 4q + 1 or 4q + 3, where q is some integer.

Sol.

Let a be any positive integer and 

b = 4. 

Now by euclid's division lemma

a = b q + r. or a = 4 q + r

where 0 ≤ r < 4.       (0, 1, 2, 3)

(i)  if r = 0

a = 4 q + 0

4q is divisible by 2 so that it is an even number.

(ii)  if r = 1

a = 4 q + 1

4q is divisible by 2 but 1 is not, so that it is an odd number.

(iii)  if r = 2

a = 4 q + 2

4q is divisible by 2 and 2 is also, so that it is an even number.

(iv)  if r = 3

a = 4 q + 3

4q is divisible by 2 but 3 is not, so that it is an odd number.

So that odd numbers will be in the form of 4q + 1 or 6q + 3, 

and 

Even numbers will be in the form of 6q or 6q + 2

Q.3 Show that every positive even integer is of the form 6q + 1; 6q + 3, or 6q + 5, where q is some integer.

Sol.

Let a be any positive integer and 

b = 6. 

Now by euclid's division lemma

a = b q + r. or a = 6 q + r

where 0 ≤ r < 4.       (0, 1, 2, 3, 4, 5)

(i)  if r = 0

a = 6 q + 0

2q is divisible by 2 so that it is an even number.

(ii)  if r = 1

a = 6 q + 1

6q is divisible by 2 but 1 is not, so that it is an odd number.

(iii)  if r = 2

a = 6 q + 2

6q is divisible by 2 and 2 is also, so that it is an even number.

(iv)  If r = 3

a = 6 q + 3

6q is divisible by 2 but 3 is not, so that it is an odd number.

(v) If r = 4

a = 6 q + 4

6q is divisible by 2 and 4 is also, so that it is an even number.

(vi) If r = 5

a = 6 q + 5

6q is divisible by 2 but 5 is not, so that it is an odd number.

So that odd numbers will be in the form of 6q + 1; 6q + 3, or 6q + 5, 

and 

Even numbers will be in the form of 6q ; 6q + 2, or 6q + 4, 

Type (3)

Q. 1 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.

Solutions:

Let a be any positive integer and 

b = 3. 

Now by euclid's division lemma

a = b q + r. or a = 3 q + r

where 0 ≤ r < 3.       (0, 1, 2)

Now ATQ

(i) If r = 0

a = 3 q + 0

a = 3 q

squaring both the sides,

a² = (3q)² 

a² = 9q² 

a² = 3 × (3q²)

Let 3q² is an integer and we are denoting it by m

Therefore, a²= 3m ……………………..(1)

(ii) If r = 1

a = 3 q + 1

a = 3q + 1

squaring both the sides,

(a)² = (3q + 1)² 

a² = (3q)²+1²+2×3q×1 

a² = 9q² + 1 +6q 

a² = 3(3q²+2q) +1

Let (3q² + 2q) is an integer and we are denoting it by m

Substitute, 3q²+2q = m, to get,

a²= 3m + 1 ……………………………. (2)

(ii) If r = 2

a = 3 q + 2

a = 3q + 2

squaring both the sides,

(a)² = (3q + 2)² 

a² = (3q)²+2²+2×3q×2 

a² = 9q² + 4 + 12q 

a² = 9q²+ 12q + 3 + 1

a² = 3 (3q² + 4q + 1)+1

Let (3q² + 4q + 1) is an integer and we are denoting it by m

Therefore, 

3 (3q² + 4q + 1) +1 = 3m + 1, to get,

a² = 3m + 1…………………………… (3)

Hence, from equation 1, 2 and 3, we can say that, the square of any positive integer is either of the form 3m or 3m + 1 for some integer m.

Q. 2. Use Euclid’s division lemma to show that the cube of any positive integer is of the form 9m, 9m + 1 or 9m + 8.

Solution:

Let a be any positive integer and 

b = 3. 

Now by euclid's division lemma

a = b q + r. or a = 3 q + r

where 0 ≤ r < 3.       (0, 1, 2)

Now ATQ

(i) If r = 0

a = 3 q + 0

a = 3 q

Cubing both the sides,

a³ = (3q)³ 

a³ = 27q³ 

a³ = 3 × (9q³)

Let (9q³)is an integer and we are denoting it by m

Therefore, a³= 3m ……………………..(1)

(ii) When r = 1, then,

a³ = (3q+1)³ 

a³ = (3q)³ +1³+3×3q×1(3q+1) 

a³ = 27q³+1+27q²+9q

a³ = 27q³+27q²+9q + 1

Taking 9 as common factor, we get,

a³ = 9(3q³+3q²+q)+1

Let (3q³+3q²+q) is an integer and we are denoting it by m

Therefore, 

a³= 9(3q³+3q²+q) +1

a³= 9m + 1…………………..(2)

(iii) When r = 2, then,

a³ = (3q+2)³ 

a³ = (3q+2)³

a³ = (3q)³+2³+3×3q×2(3q+2) 

a³ = 27q³+54q²+36q+8

Taking 9 as common factor, we get,

a³=9(3q³+6q²+4q) + 8

Let (3q³+3q²+q) is an integer and we are denoting it by m

Therefore, 

a³ = 9(3q³+6q²+4q) + 8

a³ = 9m + 8…………………..(3)

Therefore, these all the three cases explained and proved that the cube of any positive integer is of the form 9m, 9m + 1 or 9m + 8.