Question

Use Euclids division lemma to show that the square of any positive integer is either of the form $3m$ or $3m+1$ for some integer $m$.

Answer 1

Using Euclid division algorithm, we know that $a=bq+r,$ $0\le r<b$ .......(1)

Let $a$ be any positive integer, and $b=3.$

After substituting $b=3$ in equation $\left(i\right),$ $a=3q+r$ where $0\le r<3$ $r=0,1,2/$

If $r=0$ and $a=3q,$

On squaring we get,

$a^2=3\left(3q^2\right)$

$a^2=3m$, where $m=3q^2$

If $r=1$ and $a=3q+1,$

On squaring we get,

$a^2=3(3q^2+2q)+1$

$a^2=3m+1$, where $m=3q^2+2q$

If $r=2$ and $a=3q+2,$

On squaring we get,

$a^2=3(3q^2+4q+1)+1$

$a^2=3m+1$, where $m=3q^2+4q+1$

Hence, proved square of any positive integer is either of the forms $3m$ or $3m+1$ for some integer $m.$