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. 
 A: If $m\equiv0\pmod4,$ then $$x^2+y^2+1\equiv0\pmod m\implies 4\mid x^2+y^2+1$$ which is clearly impossible, so the equation has no solutions.
If $m\not\equiv0\pmod4,$ then, by multiplying by $2$ if necessary, we can reduce to the case $m\equiv2\pmod4.$ Consider the set $P=\{(mk-1\mid k\in \mathbb{Z}\}.$ If one of the elements, $p\in P$ is of the form $\prod_ip_i^{k_i}\prod_jq_j^{2l_j}$ with $p_i\equiv1\pmod 4$ and $q_j\equiv -1\pmod4,$ then by Fermat's theorem on sums of two squares,
$p$ can be written as a sum of two squares $x^2+y^2$ which shows that $m\mid x^2+y^2+1.$
If $p$ is not of that form, then without loss of generality, neglecting those $q_j$ which occur to an even exponent, we may assume it is of the form $p=\prod_ip_i^{k_i}\prod_jq_j^{2l_j+1}.$ Now consider the set $Q=\{\gamma_j:=\operatorname{ord}_mq_j\}$ (the smallest positive integer $l$ such that $q_j^l\equiv1\pmod m$). For $\gamma\in Q,$ if $\gamma$ is even, then, by Chinese remainder theorem, find $z$ such that $ \begin{cases}
z\equiv q_j\pmod{m/2}\\
z\equiv 1\pmod 4
\end{cases}.$
Then by use of Dirichlet's theorem on arithmetic progressions,
we can find a prime $q_j'$ with $q_j'\equiv z\pmod{2m}.$ Thus we have 
$$p':=p\prod\limits_{2\not\mid\gamma_j} q_j^{\gamma_j}\prod\limits_{2\mid\gamma_j}q_j^{\gamma_j-1}q_j'\equiv-1\pmod m,$$ and $p'$ is of the form $(\prod_ip_i^{k_i}\prod_{2\mid \gamma_j} q_j')\prod_{2\mid \gamma_j} q_j^{2l_j+1+\gamma_j-1}\prod_{2\not\mid\gamma_j}q_j^{2l_j+1+\gamma_j}$ where $p_i$ and $q_j'$ are $\equiv1\pmod4,$ and the exponents of the $q_j$ are even. Therefore $p'$ can be written as $x^2+y^2,$ so that $m$ divides $p'+1=x^2+y^2+1.$  

Hope this helps.
A: 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.
