Iff statement for Modulo I have a question that I've been stuck on for a long time. I wanted to see if friends at Stack Exchange can help me:
Prove that for any odd prime $p$, the congruence $x^{2}+1\equiv0(mod p)$ has a solution if and only if $x^{2}+1\equiv0 (mod p^{2})$ has a solution. So far the forwards proof is giving me some trouble. I have the following down:
Let p be an odd prime. Let n be an integer such that $n^{2}+1\equiv0(mod p)$. This means that there exists an integer k such that $n^{2}+1=pk$. We will show that there exists an integer x such that $x^{2}+1\equiv0(mod p^{2})$.
Let $x=qp+r$ for some integers q and r:
$$(qp+r)^{2}+1\equiv0 (mod p^{2})$$
Then $$2qpr+r^{2}\equiv0(mod p^{2})$$
Setting $r=n$, we get $2qpn+n^{2}+1\equiv0(mod p^{2})$.
This is as far as I have gotten. I'm stuck from this point on: can someone tell me what my next steps should be to complete the forwards proof? Thank you.
Note: this is not really a "proof verification" question since the proof is not fully complete, but I feel that I'm close enough.
 A: The obvious thing to do is apply a Hensel’s-Lemma type of argument to the situation, improving what you have by adding a suitable multiple of $p$ to get something that’s good modulo $p^2$. This is the very sound strategy that motivated you.
But let me show you a sneaky trick that is special to this situation, because the $p$-adic root of your equation $X^2+1$ is a root of unity, namely the fourth root of unity $i$ (or $-i$, naturally).
Your hypothesis is that $x^2+1\equiv0\pmod p$, and I’m about to show you that $(x^p)^2+1\equiv0\pmod{p^2}$. (Check it out for $x=2$, $p=5$.)
The hypothesis can be rewritten $x^2=pr-1$ for some integer $r$. Now,
$$
(x^p)^2=(x^2)^p=(pr-1)^p\,,
$$
and you just expand the right-hand end of this using Binomial Theorem, and see that the result is in the form $p^2R-1$ for a certain integer $R$, and that says that $(x^p)^2\equiv-1\pmod{p^2}$, as desired.
The really wonderful thing about this is that if you take the number you just got, namely $x^p$, and raise it to the $p$-th power, you get something that is an even better root of $X^2+1$.
