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

I worked it out up to 15.

6 = 4 + 2
7 = 4 + 3
8 = 6 + 2
9 = 4 + 5
10 = 8 + 2
11 = 9 + 2
12 = 10 + 2
13 = 10 + 3
14 = 9 + 5
15 = 12 + 3

Does this trend continue forever? I feel like the answer is obvious but I'm just not seeing it.

• I saw this question and started thinking it's like Goldbach's conjecture and any kind of proof would be very difficult. But such a simple explanation exists! – user230452 Feb 28 '16 at 5:39
• Alternatively you can also think of it this way: there's clearly always a prime $p$ between 1 and your integer $n$, and there's a good chance that $n - p$ is not prime; so clearly the problem isn't hard. it shouldn't be hard to work out possible values of $p$ that will systematically work for all $n$. – Thomas Feb 29 '16 at 6:24

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.

• Thanks. I feel like this was obvious and you really make it look easy. – Reggie Simmons Feb 28 '16 at 1:03
• This was brilliant. You did it so easily. – user230452 Feb 28 '16 at 1:04
• @ReggieSimmons You were a couple steps away from obvious yourself ;-) if only you had chosen different sums for 9 = 6 + 3 and 11 = 8 + 3. – dxiv Feb 28 '16 at 4:29
• The biggest take-home message from this sort of question is learning "how to think about math", not getting the answer. You probably don't know much number theory yet, so the answer is unlikely to be complicated proof that there is a counterexample greater than $10^{439}$. So, try thinking about the smallest primes, and the significance of the number $5$ in the question! (And considering odd and even numbers separately - or set of numbers like $3k$, $3k+1$, $3k+2$ - is often a good idea to try.) – alephzero Feb 28 '16 at 4:57
• @alephzero I saw this question and started thinking it's like Goldbach's conjecture and any kind of proof would be very difficult. But such a simple explanation exists! Of course, since I didn't encounter this question in a text book, I didn't think it had an easy (or any) solution at all. – user230452 Feb 28 '16 at 5:40

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.