# Is this proof correct?

The problem is "Can you find a value $n$ such that $n^2+1$ is divisible by $3$?"

My analysis: For the divisibility of $n^2+1$ by $3$, we need $n^2 \equiv 2 \pmod{3}$ in other words we need to show that $2$ is quadratic residue of $3$, but $2 \equiv -1 \pmod 3$ which imply that $2$ is quadratic non residue of $3$.Hence, no such $n$ is possible.

I recently learned about quadratic residue and this is probably my first application, so please check if I committed an error?

Thanks,

-
See also this question: math.stackexchange.com/questions/62831/… – Martin Sleziak Dec 4 '11 at 14:20

Why does pointing out that $2\equiv -1\bmod 3$ show that $2$ is a quadratic non-residue? You need to fill in your argument. Here is a simple proof that $2$ is a non-quadratic residue mod $3$: $$0^2\equiv 0\bmod 3$$ $$1^2\equiv 1\bmod 3$$ $$2^2\equiv 1\bmod 3$$ The rest of your proof is fine.

-
Reciprocity was actually a typo since I was thinking if we could apply that while typing the last part, then but I guess quadratic reciprocity is not applied here because of 2.. right? Also, $2 \equiv -1 \pmod 3$ ain't this sufficient to prove the quadratic non-residue? – Quixotic Dec 4 '11 at 14:20
Where is your proof that $-1$ is not a quadratic residue modulo $3$? Why would pointing out that $2\equiv -1\bmod 3$ show that $2$ is a quadratic non-residue? – Zev Chonoles Dec 4 '11 at 14:20
Look at supplement law 1; for an odd prime $p$, $-1$ is a quadratic residue mod $p$ iff $p\equiv 1\bmod 4$. That's what I thought you meant when you said you were using quadratic reciprocity. You're correct that you can't flip because of the $2$. – Zev Chonoles Dec 4 '11 at 14:22
I thought it is implied that if a is non-residue to b then $a \equiv -1 \pmod b$ and $a \equiv 1 \pmod b$ otherwise ... just thiking on the lines of Fermat's little theorem ain't it ? – Quixotic Dec 4 '11 at 14:23
No. Consider that $3$ and $4$ are quadratic non-residues modulo $7$. – Zev Chonoles Dec 4 '11 at 14:24

HINT $\rm\quad\ \ mod\ 3\!\!:\ n\not\equiv 0\ \Rightarrow\ n \equiv \pm1 \ \Rightarrow\ n^2 \equiv 1 \not\equiv -1$

Similarly $\rm\ mod\ 8\!\!:\ odd\ n\: \Rightarrow\ n \equiv\pm1,\pm3\ \Rightarrow\ n^2 \equiv 1,\:$ a result often of use in number theory.

Combining both we deduce $\rm\: n^2 \equiv 1\pmod{24}$ for odd $\rm\:n\:$ coprime to $3\:.\:$ More generally see here.

Note how work is halved using the balanced residue system $\rm\: 0,\pm1,\pm2,...,\pm\lfloor m/2\rfloor\pmod m$

-