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.

Using Euclid division algorithm, we know that a = bq + r, 0 ≤ r < b.. (1)
Let a be any positive integer, and b = 3.
After substituting b = 3 in equation (1), a = 3q + r where 0 ≤ r < 3
r = 0, 1, 2
If r = 0 and a = 3q,
On squaring we get, a² = 3(3q²)
a² = 3m, where m = 3q²
If r = 1 and a = 3q + 1,
On squaring we get, a² = 3(3q² + 2q) + 1
a² = 3m + 1, where m = 3q² + 2q
If r = 2 and a = 3q + 2,
On squaring we get, a² = 3(3q² + 4q + 1) + 1
a² = 3m + 1, where m = 3q² + 4q + 1
Hence, proved square of any positive integer is either of the forms 3m or 3m + 1 for some integer m.