Coprimer 2016

By Chebyshev's Theorem (sometimes oddly called "Bertrand's Postulate" in the West), for every even number $n>6$ there exists a prime $p$ with $\frac{n}{2}<p<n-1$ . We can write $n=p+(n-p)$ , with $\gcd(p,n-p)=1$ . For $n=4$ and $n=6$ there is no representation of the required form, so that the answer is $\boxed{2}$ . (For odd numbers we can write $2n+1=n+(n+1)$ , of course.)

The only numbers that will not work are $4$ and $6$ , which can be verified via the trial-and-error process. Every odd number would work as they can be described as the sum of $2$ and another odd number, and $2$ and any odd number are coprime. Same thing goes for those not divisible by $3$ —add $3$ to a number not divisible by $3$ . This process works for all numbers greater than $6$ , as for all numbers $n>6$ , there's always a prime number $p<\frac{n}{2}$ that does not divide $n$ .