I've been having trouble with the following congruence, finding all primes $p$ for $$x^2 + 1 \equiv 0\ mod\ p^2$$
By the definition of quadratic reciprocity, I know that $-1$ is a quadratic residue $mod\ p$ exactly when $p$ is $1\ mod\ 4$, which means that $x^2 + 1$ has a solution to this congruence.
I also know that $x^2 + 1$ cannot have a root $mod\ p^2$ if $p$ is $3\ mod\ 4$, since then $\phi(p)$ is not divisible by $4$.
My question is where do I go from here? I'm probably going to need a little help as far as comprehension goes as well.
(don't forget to check $p=2$)
Take the information you know and simplify the problem. If you know that $x^2 + 1$ has two roots $\pm a$ modulo $p$, then if $x^2 + 1$ has a root $b$ modulo $p^2$, then $b \equiv a \bmod p$ or $b \equiv -a \bmod p$.
If $b \equiv a \bmod p$, that means $b = a + pc$ for some integer $c$. Using this information simplifies the problem greatly. Repeat for the $b \equiv -a \bmod p$ case.
P.S. for a completely different approach, have you considered finding the group structure of the unit group modulo $p^2$? Or even just $\varphi(p^2)$?
As an interesting aside, from $p$-adic analysis we can learn that we can use Newton's method to find the roots of $f(x) = x^2 + 1$! If $a^2 = 1 \bmod p$, then we know the square root of $-1$ to one $p$-adic digit. To get more precision, we iterate
$$a' = a - \frac{f(a)}{f'(a)} $$
It turns out that if $a^2 + 1 \equiv 0 \bmod {p^n}$, then $(a')^2 + 1 \equiv 0 \bmod p^{2n} $.
This probably isn't how you should attack the problem, but I thought it is still interesting t oknow.
(with care regarding what it might mean to divide by $2$, you can use the above for $p=2$ too, although it doesn't converge as quickly: it goes from $p^n$ to $p^{2n - 1}$)