# $f(n)+f(m) = q^2$ always has a solution

Prove or disprove: Let $$f$$ be a non-constant polynomial with nonnegative integer coefficients. Then there exist $$m,n \in \mathbb{N}$$ such that $$f(n)+f(m)$$ is a perfect square.

I'm just posting this because I noticed the pattern, and I cannot find a counterexample for some reason, although I'm sure there is one somewhere.

This is false; consider $$f(x)=x^4$$. It is a theorem of Fermat that a sum of two positive fourth powers is never a square, a proof can be found here. If you allow $$0\in\Bbb{N}$$ then you can instead take $$f(x)=(x+1)^4=x^4+4x^3+6x^2+4x+1.$$
Easier example: let $$f(x)=4x+1$$. Then $$f(n)+f(m)\equiv 2\pmod 4$$, but no square can be even but not divisible by $$4$$.
Inspired by @Wojowu's answer, observe that the only possible quadratic residues mod $$8$$ are $$\{0, 1, 4\}$$. Thus, if $$f(x)\equiv_{\pmod 8} \begin{cases} 1\\ 3\\ 5\\ 7 \end{cases}$$ then $$f(n)+f(m)$$ won't be an perfect square. Examples are $$f(x)=8x+n$$ where $$n$$ is an odd integer.
• This can be generalized vastly, take any $a,b$ such that $2a$ is not a square modulo $b$, then we can take $bx+a$. For instance, $3x+1$ will work. – Wojowu Mar 31 at 16:52