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.

score 4 · Answer 1 · answered Jan 12 '20 at 14:18

4

Guide:

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

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

answered Jan 12 '20 at 14:18

Siong Thye Goh

149,520
20
88
149

I dont understand. Why 2 can not a remainder. May you tell clearly ? – David Jan 12 '20 at 14:30
We have covered every single case right? and none of them is $2$? – Siong Thye Goh Jan 12 '20 at 14:40

score 1 · Accepted Answer · answered Jan 12 '20 at 14:49

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.

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

2 Answers2