Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
See also this question:… – Martin Sleziak Dec 4 '11 at 14:20
up vote 2 down vote accepted

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.

share|cite|improve this answer
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$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.