Number of solutions of $m^2 + 1 \equiv 0 \pmod{n}$ in modulo $n$. yay If $4|n$ or $p|n$ with $p=4k+3$, the answer is clearly $0$. If not, the answer is $2^{\text{number of odd primes of n}}$. First, let us take care of $2|n$. It just determines whether or not $m$ is even or not. So we are left with $p^e$ where $p=4k+1$. Let us solve $m^2 \equiv -1 \pmod{p^e}$. CRT will do the rest. If $m^2 \equiv n^2 \pmod{p^e}$ and $(m,p)=1$, we have $m \equiv \pm n \pmod{p^e}$. So the equation has either $0$ or $2$ solutions. But it is easy to see that there are two solutions by Hensel. Done.

What is Hensel's lemma ?

kk108 wrote: What is Hensel's lemma ? Don't hesitate to use that new thing called The Internet..

Tintarn wrote: kk108 wrote: What is Hensel's lemma ? Don't hesitate to use that new thing called The Internet.. Thank you !

fractals wrote:

You don't need Hensel's Lemma here. You can prove this using elementary methods. You want to prove that if $p\equiv 1\pmod{4}$ is prime, then there are exactly two solutions to $x^2 + 1 \equiv 0 \pmod{p^k}$. There is at least one solution because $x^2+1\equiv 0\pmod{p}$ is solvable by Quadratic Reciprocity and by the proof in the website below (if $p\equiv 1\pmod{4}$, then $p$ is an odd prime, and clearly $p\nmid -1$). https://en.wikipedia.org/wiki/Quadratic_reciprocity#.C2.B11_and_the_first_supplement http://math.stackexchange.com/questions/1429863/prove-that-quadratic-residual-mod-p-rightarrow-quadratic-residual-mod-pn/1430792#1430792 If $a$ is a solution to $x^2+1\equiv 0\pmod{p^k}$, then $-a$ is also a solution, and $a\not\equiv -a\pmod{p^k}$, because otherwise $p^k\mid 2a$, which is impossible, because $p$ is odd and $\gcd(p,a)=1$ because $\gcd(p,-1)=1$. $x_1^2+1\equiv x_2^2+1\pmod{p}$ if and only if $p\mid x_1^2-x_2^2=(x_1+x_2)(x_1-x_2)$ if and only if $x_1\equiv \pm x_2\pmod{p}$ by Euclid's lemma, which means there can't be another third solution. Done.

$p|n$ $p|m^2+1$ $p=4k+1$ or $p=2$ $t$ is number of odd primes of $n$ by C.R.T answer: $2^t$