Can every integer greater than 5 be written as the sum of exactly one prime and one composite?

Solution 1:

If $n$ is even, then $n=2+(n-2)$, and $n-2$ is even, so it is a composite number. If, now, $n$ is odd, $n=3+(n-3)$, and $n-3$ is even.

Solution 2:

After seeing @detnvvp's brilliant answer to this question, one is left to wonder if it can be generalized.

Theorem: For natural number $k$, every sufficiently large number $n$ is a sum of a prime number and a multiple of $k$ iff $k=1$ or $k$ is prime.

Proof: The problem reduces to finding a prime $p_i=i\pmod k$ for each $0\le i<k$, for then we can take $n=p_i+(n-p_i)$ whenever $n\equiv i\pmod k$, so that $k\mid n-p_i$. For $k=1$, $p_0=2$ works, and detnvvp's answer covers the case $k=2$ with $p_0=2$ and $p_1=3$. Continuing, we have, for $k=3$: $p_0=3,p_1=7,p_2=2$.

More generally, if $k$ is prime, then we can take $p_0=k$, and for each $0<i<k$ we have $\gcd(i,k)=1$, so by a theorem of Dirichlet, there are infinitely many primes in the arithmetic progression $i,i+k,i+2k,\dots$, and we can pick one of them to be $p_i$.

If $k$ is composite, then there is no possible choice for $p_0$. For each $n$ that is a multiple of $k$, we must sum a prime and a multiple of $k$ to get a multiple of $k$, so the prime must also be a multiple of the composite number $k$, a contradiction. $\tag*{$\square$}$

For $k$ composite, the same method as in the prime case allows us to find $p_i$ for $\gcd(i,k)=1$, and we can also take $p_q=q$ for each prime divisor of $k$, but for all other $i$ there is no solution. By combining this for different choices of $k$, we get stronger results:

Theorem: There is no finite set of composite numbers $K$ such that every sufficiently large number is the sum of a prime number and a multiple of some $k\in K$. (Hint: Consider the multiples of $\prod_{k\in K} k$.)

What if we don't fix the factors, but just demand that the composite number have at least $m$ factors? Here the method of congruences does not seem to be as effective, and I don't know the answer, although I would conjecture that it is true:

Conjecture: For each $m$, every sufficiently large number $n$ is the sum of a prime number and a number with at least $m$ factors.