this is a really beautiful problem ,my solution: Define a set ${a_{(m,n)}=f(m)-f(n)}$ we want to prove that for any $m,n,k,l \in N$ there exist a $r,s$ such that : $a_{(m,n)}+a_{(k,l)}=a_{(r,s)} , a_{(m,n)}-a_{(k,l)}=a_{(r,s)}$ $ f(m)+f(n)+f(f(m^2+n^2))=1 \Longrightarrow f(n)+f(f(m^2+n^2))=f(t)+f(f(t^2+m^2)) \Longrightarrow f(n)-f(t)=f(f(t^2+m^2))-f(f(m^2+n^2)) $ $a_{(m,n)}+a_{(k,l)}=f(m)-f(n)+f(k)-f(l)=f(f(l^2+n^2))-f(f(l^2+m^2))+f(f(l^2+m^2))-f(f(k^2+m^2))=f(f(l^2+n^2))-f(f(m^2+k^2))=a_{(r,s)}$ so just like this we can prove this $a_{(m,n)}-a_{(k,l)}=a_{(r,s)}$ so now this is a ring that we have plus and minus so we have multiple too now assume that there exist $m,n$ such that $a_{(m,n)}=3$ so there exist a $r,s$ that $a_{(r,s)}=3k$ if $\forall m,n :a_{(m,n)} \mod{3}=0$ then $1=f(m)+f(n)+f(f(m^2+n^2)) \mod{3} =0$ is a contradiction so there exist $a_{(l,t)}=3k+1$ so $a_{(l,t)}-a_{(r,s)}=1$ and contradiction,so we are done

Here's a less beautiful solution. Let $S$ be the range of $f$. Lemma: $x, x+3 \in S \implies x-3 , x+6 \in S$. Proof: Since $f(f(m^2+n^2)) = 1-f(m)-f(n)$, if $y_1, y_2 \in S$, then $1-y_1-y_2 \in S$. Therefore, since $x \in S, 1-x-x = 1-2x \in S$. Then $1-(1-2x)-(x+3) = x-3 \in S$. Similarly, $1-(x+3)-(x+3) = -2x-5 \in S$. Therefore, $1-(-2x-5)-(x) = x+6 \in S$. Now we have 3 cases: $x \equiv 0, 1, 2 \pmod{3}$. If $x \equiv 0 \pmod{3}$, by the Lemma, $0 \in S$. So $1-0-0 = 1 \in S$. Since $1-0 = 1$, this case is done. If $x \equiv 1 \pmod{3}$, by the Lemma, $1, 4 \in S$. Since $1 \in S, 1-1-1 = -1 \in S$. Therefore, $1-(-1)-(-1) = 3 \in S$. But $4-3 = 1$, so this case is done. If $x \equiv 2 \pmod{3}$, by the Lemma, $2, -1 \in S$, so $1-(-1)-(-1) = 3 \in S$. Since $3-2 = 1$, this case is done.

Consider the set $S= \{f(a)-f(b) \quad a,b \in \mathbb Z\}.$ It is given that $3 \in S$ . We want to show that $1 \in S$ . Claim : $S$ is closed under addition . Pick $s_1,s_2 \in S$ . Assume that $s_1=f(a_1)-f(a_2)$ and $s_2=f(b_1)-f(b_2)$ Note that we have :$$f(a_1)+f(b_1)+f(f(a_1^2+b_1^2))=1$$$$f(a_2)+f(b_2)+f(f(a_2^2+b_2^2))=1$$Subtracting the two equations gives : $$s_1+s_2 = f(f(a_2^2+b_2^2))-f(f(a_1^2+b_1^2))\in S$$ The claim is hence true .$\blacksquare$ Next note that : $$s=f(x)-f(y) \in S \implies f(y)-f(x) \in S \implies -s \in S$$ Hence $S$ is closed under both addition and subtraction . It is easy to show that $S= n\mathbb Z$ for some $n \in \mathbb Z_{\geq 0}$ . This is proved by taking the smallest difference $d$ between two elements of $S$ and showing that $d$ divides all other differences of elements of $S$ . Hence since $n\mid 3$ ,so either $S \equiv \mathbb Z$ or $S \equiv 3 \mathbb Z$ . In the first case the problem statement is obvious. For the second case note that $f(x) \equiv r \pmod 3$ $\forall x \in \mathbb Z$ , for some $r \in \{0,1,2\}$ . Hence $$1=f(a)+f(b)+f(\text {blah})\equiv 3r \equiv 0 \pmod 3$$We reach the desired contradiction. $\blacksquare$

Solved with eisirrational, goodbear, Th3Numb3rThr33. Let \(S\) denote the range of \(f\). If \(a,b\in S\), then \(1-a-b\in S\). We can now safely throw away the rest of the functional equation. Let \(c,c+3\in S\). We have \(1-2c\), \(1-2c-3\) ,\(1-2c-6\) are in \(S\), so \(c-3\), \(c+6\) are in \(S\). Repeating with \(c-3,c\in S\) and \(c+3,c+6\in S\), and so on, all \(n\) with \(n\equiv c\pmod3\) are in \(S\). Repeating for \(1-2c\), \(1-2c-3\), etc., all \(n\) with \(n\equiv1-2c\pmod3\) are in \(S\). The equivalence classes \([c\pmod3]\) and \([1-2c\pmod3]\) are distinct, so they contain two consecutive elements, end proof.