2
$\begingroup$

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,

  • 0
    See also this question: http://math.stackexchange.com/questions/62831/would-like-a-proofreading-of-my-proof2011-12-04

2 Answers 2

2

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.

  • 0
    Cool!! Quadratic reciproicity seems to be$a$major theorem, I was actually reading it from "what is Mathematics?" although this book is very good but it doesn't provide much insight in this topic, can you suggest me any book/reference which provides sufficient information and yet not complicated...2011-12-04
0

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$