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

## Solution :

By Euclid’s Division Algorithm, we have

a = bq + r       …………..(i)

On putting b = 3 in (1), we get

a = 3q + r,      [0 $$\le$$ r < 3]

If r = 0   a = 3q  $$\implies$$  $$a^2$$ = $$9q^2$$                       …..(2)

If r = 1  a = 3q + 1   $$\implies$$  $$a^2$$ = $$9q^2 + 6q + 1$$                       …..(3)

If r = 2   a = 3q + 2    $$\implies$$  $$a^2$$ = $$9q^2 + 12q + 4$$                       …..(4)

From (2), $$9q^2$$ is a square of the form 3m, where m = $$3q^2$$

From (3), $$9q^2 + 6q + 1$$  i.e. , 3($$3q^2 + 2q$$) + 1 is a square which is of the form 3m + 1 where m = $$3q^2 +2q$$

From (4), $$9q^2 + 12q + 14$$  i.e. , 3($$3q^2 + 2q + 1$$) + 1 is a square which is of the form 3m + 1 where m = $$3q^2 +4q + 1$$

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