Show $x^2 + y^2 + 1 = 0 \pmod m$, iff $\,m \pmod 4 \ne 0$. 
Show that $x^2 + y^2 + 1 = 0$ $\pmod m$ has solutions iff $\,m \pmod 4
 \ne 0$.

I know hot to show that this equation has solutions if m = p It's easy to show "$=>$", but I'm completery stucked with the opposite direction. 

If $m \equiv 0\pmod 4$ it is simple to prove there is no solution, test all possible pairs $(x,y)$. If $2m \equiv 2\pmod 4$ then a solution can be constructed by the chinese remainder theorem from the solution of the odd $m$ and the solution $x=0,y=1$ modulo $2$. So we assume that $m$ is odd.
If $m$ is a prime then $\frac{m+1}{2}$ of the numbers $0,\ldots,m-1$ are squares. Therefore both sets $\{-x^2\mid x=0,\ldots\ m$ and $\{y^2+1\mid y=0,\ldots\ m$} contain $\frac{m+1}{2}$ elements. So the intersection of these sets is not empty. So there is a $x$ and a $y$ such that $y^2+1=-x^2$ if $m$ is an odd  prime.
Now by induction we show that the equation has a solution for every power of an odd prime.
If $(x,y)=(x_0,y_0)$ is a solution of 
$$x^2+y^2+1 \equiv 0\pmod{p^n}$$
then 
$$x_0^2+y_0^2+1=q_0p^n$$
Therefore 
$$ \begin{align}(x_0+ap^n)^2+(y_0+bp^n)^2+1&=x_0^2+y_0^2+1+2p^n(ax_0+by_0)+(a^2+b^2) p^{2n}\\&=p^n(q_0+2ax_0+2by_0)+p^{n+1}(a^2+b^2)p^{n-1}\\
&=p^n(pt)+p^{n+1}(a^2+b^2)p^{n-1}\\
&\equiv 0 \pmod {p^{n+1}}\end{align}$$
because the equation 
$$q_0+2ax_0+2by_0 \equiv 0 \pmod{p}$$
has a solution $(a,b) \pmod p$ and therefore 
$$q_0+2ax_0+2by_0=tp$$. 
Here is the proof:
At leas oen of $x_0$ or $y_0$ is not equal to $0$, so let's assume $x_0 \ne 0$. So we select an arbitrary b and get 
$$a=\frac{2by_0-q_0}{2x_0} \pmod{p}$$
We have shown that there is a solution if $m$ is a power of an odd prime. By the chinese remainder theorem we can construct a solution for $m$ that is a product of odd prime powers.
