Prove that the division of the square of an integer by 3 never yields 2 as the remainder.

Question

I tried to conclude contradiction.I said n^2=2 (mod 3) . But I couldn't find a Contradiction.How Can I solve this question.

Answer 1

Any integer can be expressed as either $3k,3k+1$ or $3k+2$. When you square these you obtain:

$9k^2$ which is divisible by $3$

$9k^2+6k+1=3(3k^2+2k)+1$ which has remainder $1$

$9k^2+12k+4=3(3k^2+4k+1)+1$ which also has remainder $1$.

So none have remainder $2$.

The method used by @SiongThyeGoh is a very efficient way to do this type of problem. So it is a good idea to become proficient in using modular arithmetic.

Answer 2

Guide:

If $n \equiv 0 \pmod{3}$, what is $n^2 \pmod{3}$?

Also inspect the cases when $n \equiv \pm 1 \pmod{3}$.