http://www.mathlinks.ro/viewtopic.php?t=48206

Peter wrote: Let $n$ be a positive integer. Prove that the following two statements are equivalent. $n$ is not divisible by $4$ There exist $a, b \in \mathbb{Z}$ such that $a^{2}+b^{2}+1$ is divisible by $n$. One direction is easy, if $4 |n$ and there exist $a,b \in \mathbb{Z}$ such that $n|a^2+b^2+1$, then $a^2+b^2+1 \equiv 0 \pmod{4}$, which easily gives a contradiction. For the second direction, assume $4 \nmid n$. We need to show the existence of integers $a,b$ such that $a^2+b^2+1 \equiv 0 \pmod{n}$. First assume that $n$ is odd. Consider the system ($p$ is a prime) $$\left\{\begin{array}{l}p \equiv 1 \pmod{4}\\p \equiv -1 \pmod{n}\end{array}\right.$$Since $(4,n)=1$, hence the system has a solution. By the first equation, we further get, by Fermat's two square theorem, that there exist $a,b \in \mathbb{Z}$ such that $p=a^2+b^2$. Hence, the second equation gives us $n|p+1=a^2+b^2+1$, as desired. Note that this method yields that $p$ is odd, and so $a^2+b^2+1$ is even. Thus, $2n|a^2+b^2+1$ is also true, and since we can do this for all $n$, hence we have also covered the case of even integers as well. This completes the proof. $\square$

For $2\implies 1$, simply assume that $n\mid a^2+b^2+1$ for some $a,b$. If $4\mid n$, we have a contradiction, since $a^2+b^2\equiv -1\pmod{4}$ is not solvable. For the other direction, we will proceed as follows. Let $p_1,p_2,\dots,p_k$ be prime divisors of $n$, with multiplicities $t_1,\dots,t_k$. If $p_1=2$, then $t_1=1$, and we can simply let $a\equiv 1\pmod{2}$ and $b\equiv 0\pmod{2}$. Hence, it suffices to consider the odd prime divisors. We now claim that, for every prime $p$, there exists $a,b$ such that, $p\mid a^2+b^2+1$. To prove this, consider the sets $$ S_1=\{a^2:a=0,1,\dots,p-1\}\quad\text{and}\quad S_2=\{-b^2-1:b=0,1,\dots,p-1\} $$in $\mathbb{Z}_p$. Clearly, $|S_1|=|S_2|=\frac{p+1}{2}$, and therefore, since their union has a cardinality at most $p$, we deduce that $|S_1\cap S_2|\geq 1$, finishing the claim. Now, to conclude the argument, we claim that for every prime $p$, and every $n$, there are numbers $a,b$ such that, $p^n\mid a^2+b^2+1$. We will prove this fact by induction on $n$. Base case is clear. For $n=2$, let $a,b$ be such that $p\mid a^2+b^2+1$. Let $a^2+b^2+1=pi$. Consider $a'=kp+a$, $b'=\ell p +b$ for some $k,\ell$ to be determined later. Notice that, $$ p^2\mid a'^2+b'^2+1 \iff p\mid 2ka + 2\ell b+i. $$Clearly, such a choice of $k,\ell$ is possible. Similar to above, in order to prove for $p^n$, let $a'=kp^{n-1}+\widetilde{a}$, and $b'=\ell p^{n-1}+\widetilde{b}$, with $p^{n-1}\mid \widetilde{a}^2+\widetilde{b}^2+1$. One can easily check that, $k$ and $\ell$ should be prescribed such that, $2k\widetilde{a}+2\ell\widetilde{b}+i$ is divisible by $p$, which can clearly be done.