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:

Let a be any odd positive integer. We apply the division lemma with a and $b=3$. Since $0 \leq r<3$, the possible remainders are 0,1 and 2 . That is, a can be $3 \mathrm{q}$, or $3 \mathrm{q}+1$, or $3 \mathrm{q}+2$, where $\mathrm{q}$ is the quotient.

Now, $\quad(3 q)^{2}=9 q^{2}$

which can be written in the form 3m, since 9 is divisible by 3

Again, $(3 q+1)^{2}=9 q^{2}+6 q+1=3\left(3 q^{2}+2 q\right)+1$

which can be written in the form $3 \mathrm{~m}+1$ since $9 \mathrm{q}^{2}+6 \mathrm{q}$, i.e., $3\left(3 \mathrm{q}^{2}+2 \mathrm{q}\right)$ is divisible by 3 .

Lastly, $(3 q+2)^{2}=9 q^{2}+12 q+4$

$=\left(9 q^{2}+12 q+3\right)+1$

$=3\left(3 \mathrm{a}^{2}+4 \mathrm{a}+1\right)+1$

which can be written in the form $3 m+1$, since

$9 q^{2}+12 q+3$, i.e., $3\left(3 q^{2}+4 q+1\right)$ is divisible by 3

Therefore, the square of any positive integer is either of the form $3 \mathrm{~m}$ or $3 \mathrm{~m}+1$ for some integer $\mathrm{m}$.