Question

use euclids division lemma to show that the square of any positive integer is of the form 3p,3p+1 or 3p+2

Answer 1

Answer:

Let a is any positive integer and b = 3

Since we know by Euclid algorithm, if a and b are two positive integers, there exist unique integers q and r satisfying

a = bq + r where 0 <= r < b

Here b = 3, then

a = 3q + r where 0 <= r < 4

Since 0 <= r < 3, then possible remainder are 0, 1 and 2

Case 1. a = 3q

=> a = 9q2

       = 3 * (3q2 )

      = 3p              {here p = 3q2 } 

Case 2. a = 3q + 1

=> a = (3q + 1)2

       = 9q2 + 6q + 4

      = 3(3q2 + 2q) + 1      

      = 3m + 1       {here p = 3q2 + 2q} 

Case 3. a = 3q + 2

=> a = (3q + 2)2

       = 9q2 + 12q + 4

       = 9q2 + 12q + 3 + 1

      = 3(3q2 + 4q + 1) + 1      

      = 3m + 1       {here p = 3q2 + 4q + 1} 

Hence, from all above cases, it is clear that square of any positive integer is either of the form 3p or 3p + 1