Use Euclid's division lemma to show that the square of any positive integer is either of the form $3mor3m+1$ for some integer $m$.

Let us consider a positive integer $a$

Divide the positive integer $a$ by $3$, and let $r$ be the reminder and $q$ be the quotient such that

We know that According to Euclid’s Division Lemma

$a=bq+r${ condition for $ris(0\le r<b)$}

$a=3q+r—————\left(i\right)b=3$

so $r$ is an integer which lies in between $0and3$

Hence $r$ can be either $0,1or2$.

Case I - When $r=0$, the equation $\left(1\right)$ becomes

$a=3q$

Now, squaring both the sides, we get

$$\begin{gathered} a^2={\left(3q\right)}^2 \\ {a}^2=9q^2 \\ {a}^2=3\left(3q^2\right) \\ {a}^2=3mWhere3q^2=m \end{gathered}$$

Case II- When $r=1$, the equation $\left(1\right)$ becomes

$a=3q+1$

Now, cubing both the sides, we get

$$\begin{gathered} a^2={\left(3q+1\right)}^2 \\ {a}^2={\left(3q\right)}^2+1^2+2\left(3q\right)\left(1\right) \\ {a}^2=9q^2+6q+1 \\ {a}^2=3\left(3q^2+2q\right)+1 \\ {a}^2=3m+1Where\left(3q^2+2q\right)=m \end{gathered}$$

Case III- When $r=2$, the equation $\left(1\right)$ becomes

$a=3q+2$

Now, cubing both the sides, we get

$$\begin{gathered} a^2={\left(3q+2\right)}^2 \\ {a}^2={\left(3q\right)}^2+2^2+2\left(3q\right)\left(2\right) \\ {a}^2=9q^2+12q+4 \\ {a}^2=3\left(3q^2+4q+1\right)+1 \\ {a}^2=3m+1Where\left(3q^2+2q+1\right)=m \end{gathered}$$

∴ square of any positive integer is of form $3mor3m+1$.

Hence proved.