$\forall n \in \mathbb{N}_{>5}\implies\exists (a,b)\in \mathbb Z^+:a^2+b^2\notin\mathbb P\;\wedge\;n=a+b$

Question

Conjecture:
$\forall n \in \mathbb{N}_{>5} \implies\exists (a,b)\in \mathbb Z^+:a^2+b^2\notin\mathbb P\;\wedge\;n=a+b$

Tested $\forall n\leq 100,000$. Small exceptions: {1,2,3,5}.

I would like to see proofs or counterexamples.
The conjecture seems to be related to:
Most even numbers is a sum $a+b+c+d$ where $a^2+b^2+c^2=d^2$
Any odd number is of form $a+b$ where $a^2+b^2$ is prime

Answer 1

If $n=5m$ with $m>1$ then $n=4m+m$ and $(4m)^2+m^2=17m^2$ is composite because $m^2>1.$

If $n\equiv 4 \pmod 5$ then $(n-1)^2+1^2>(n-1)^2\geq 3^2>5$ and $(n-1)^2+1^2 \equiv 0\pmod 5.$

If $5<n\equiv 1\pmod 5$ then $(n-2)^2+2^2>(n-2)^2\geq 4^2>5$ and $(n-2)^2+2^2\equiv 0\pmod 5.$

If $5<n\equiv 3\pmod 5$ then $(n-2)^2+2^2>(n-2)^2\geq 6^2>5$ and $(n-2)^2+2^2\equiv 0 \pmod 5.$

If $5<n\equiv 2 \pmod 5$ then $(n-4)^2+4^2>(n-4)^2\geq 3^2>5$ and $(n-4)^2+4^2\equiv 0\pmod 5.$

Answer 2

We are looking for $n$ such that the quadratic polynomial $$\tag1 x^2+(n-x)^2\qquad(=2x^2-2nx+n^2)$$ is prime for surprisingly many integers $x$. It is well-known folklore that the polynomial $$\tag2 x^2+x+41$$ is prime for surprisingly many integers $x$. What is less (publicly) known is that this coincidence is owed to the fact that the discriminant of $(2)$, $-163$, has class number $1$ (which is rare). The discriminant of $(1)$ is $-n^2$ and therefore hardly of class number $1$.

To make this argument water-tight, one would have to elaborate more on the relation between class numbers and represented primes ...

Answer 3

This is not a solution, but it's too long for a comment.

As I wrote in the comment above, if $n$ is composite, then the statement is easily proved. Write $n=x \cdot y$ and pick $(a,b)=(x, xy-x)$. Since $$a^2+b^2=x^2(1+(y+1)^2)$$ is divisible by $x^2$, it's not a prime.

This reduces the study of this problem to primes $n \ge 7$.

This is equivalent to the following:

$$\exists a \in \left\{ 1, \dots , \frac{n-1}{2} \right\}: \ a^2+(n-a)^2 \mbox{ is composite}$$

Now, for all $a \in \left\{ 1, \dots , \frac{n-1}{2} \right\}$, call $$s=n-2a$$ Note that $s$ is odd and that $s \in \left\{ 1, 3, 5, \dots , n-2 \right\}$. Then $$\frac{n^2+s^2}{2} = \frac{2n^2-4an+4a^2}{2} = n^2-2an+2a^2 = a^2+(n-a)^2$$ which is composite for a suitable option for $s$.

Hence your conjecture is equivalent to the following:

For all primes $n \ge 7$ there exists an odd integer $s \in \{ 1, \dots , n-2\}$ such that $\frac{n^2+s^2}{2}$ is composite.