Question

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, but not of the form $3m+2$.

Answer 1

Let $a$ be the positive integer and $b=3$.

We know $a=bq+r$, $0\le r<b$

Now, $a=3q+r$, $0\le r<3$

The possibilities of remainder is $0,1,$ or $2$.

Case 1 : When $a=3q$

$a^2=(3q{)}^2=9q^2=3q\times 3q=3m$ where $m=3q^2$

Case 2 : When $a=3q+1$

$a^2=(3q+1{)}^2=(3q{)}^2+(2\times 3q\times 1)+(1{)}^2=3q(3q+2)+1=3m+1$ where $m=q(3q+2)$

Case 3: When $a=3q+2$

$a^2=(3q+2{)}^2=(3q{)}^2+(2\times 3q\times 2)+(2{)}^2=9q^2+12q+4=9q^2+12q+3+1=3(3q^2+4q+1)+1=3m+1$

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

Hence, from all the above cases, it is clear that square of any positive integer is of the form $3m$ or $3m+1$.