** **Use Euclid's Division Algorithm to show that the square of any positive integer is either of the form 3m or 3m + 1 for some integer m.

#### Solution

Let **a **and **b** are two positive integers such that **a** is greater than **b**; then:

a = bq + r; where q and r are also positive integers and 0 ≤ r < b

Taking b = 3, we get:

a = 3q + r; where 0 ≤ r < 3

⇒ The value of positive integer **a** will be

3q + 0, 3q + 1 or 3q + 2

i.e., 3q, 3q + 1 or 3q + 2.

Now we have to show that the squares of positive integers 3q, 3q + 1 and 3q + 2 can be expressed as 3m, or 3m + 1 for some integer m.

**Square of 3q **= (3q)^{2 }

= 9q^{2} = 3(3q^{2}) = 3m; 3 where m is some integer.

**Square of 3q + 1** = (3q + 1)^{2}

= 9q^{2} + 6q + 1

= 3(3q^{2} + 2q) + 1 = 3m + 1 for some integer m.

**Square of 3q + 2** = (3q + 2)^{2}

= 9q^{2} + 12q + 4

= 9q^{2} + 12q + 3 + 1

= 3(3q^{2} + 4q + 1) + 1 = **3m + 1** for some integer m.

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

**Hence the required result.**