$\forall n \in \mathbb{N}_{>5}\implies\exists (a,b)\in \mathbb Z^+:a^2+b^2\notin\mathbb P\;\wedge\;n=a+b$ 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
 A: 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 ...
A: 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.

A: 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.$
