# Prove that every integer $n\geq 7$ can be expressed as a sum of distinct primes.

My teacher said to use Bertrand's postulate and I have tried this for so long and I seem to go nowhere. Help would be appreciated.

EDIT: Here's what I've done in my proof so far (I need help finalizing case 2)

First note that for $p_0=13$, we can express all integers $7 \leq n \leq 2p_0=26$ as a sum of distinct primes less than or equal to $13$. Now, we will prove that we can construct these sums indefinitely. Assume we know some prime $p'$ exists such that every integer $7\leq n \leq 2p'$ can be expressed as a sum of distinct primes less than or equal to $p'$. Then, by Bertrand's postulate, there exists a prime $p$ such that $p'<p<2p'$. We claim now that every integer $7\leq n \leq 2p$ can be written as a sum of distinct primes less than or equal to $p$. Consider the two following cases

Case 1: $2p'-p\geq 7$, hence $2p'\geq p+7$ so the terms $p,p+1,\dots,p+7$ are less than or equal to $2p'$ which means they can be written as a sum of distinct primes $\leq p'$ by hypothesis. It is left to check whether the terms $p+8,p+9,\dots, 2p$ satisfy our claim. Note if we subtract $p$ from every term in the arithmetic progression above, it becomes $8,9,\dots, p<2p'$ which shows that each term can be written as the sum of $p$ plus some other distinct primes less than or equal to $p'<p$ by hypothesis.

Case 2: $2p'-p\leq 6$, hence $2p'\leq p+6$. Here we can see all terms $p+7,\dots, 2p$ satisfy our claim along with $p+2,p+3$ and $p+5$ by a similar argument as in Case 1. I'm not sure how to deal with $p+1,p+4,$ and $p+6$ though.

EDIT: Oh, since any prime $p \geq 13$ is odd, then the only possible values for $2p'$ in Case 2 are $p+1,p+3$ and $p+5$, so I don't have to worry about the other cases. I think I'm done!

EDIT: Nope, I still need to deal with $p+4$ and $p+6$.

• Use strong induction. – DeepSea Aug 3 '15 at 4:10
• I don't think this is easy (though I could be wrong). At first I thought you could use Bertrand to find a prime $p$ with $[\frac n2]<p<n$. Then, defining $m$ by $n-p=m$ you just inductively write $m$ as a sum of distinct primes (it is less than $p$ so you know $p$ doesn't appear twice). Alas, I see no reason why $m$ might not be $1$, $4$, or $6$ any of which would make the argument fail. – lulu Aug 3 '15 at 4:17
• Seems to be known as Richert's Theorem. Not horribly difficult, but not straight forward either. I couldn't find his original paper but here is a proof: matwbn.icm.edu.pl/ksiazki/aa/aa41/aa4117.pdf – lulu Aug 3 '15 at 4:33

We shall inductively prove a stronger form, namely that every positive integer $n \ge 7$ can be written as the sum of distinct primes such that the largest is at most $\max(11,n-7)$. It turns out that strengthening makes the induction work!

Take $n \ge 28$.

Let $m = \lceil \frac{n-6}{2} \rceil= \lfloor\frac{n-5}{2} \rfloor$.

Let $p$ be a prime such that $m+1 \le p \le 2m-1$ [by Bertrand's postulate].

Then $\frac{n-5}{2} \le p \le n-7$.

By the induction to be established $n-p$ can be written as a sum of distinct primes such that the largest is at most $\max(11,n-p-7)$, which is less than $p$ because $p \ge \frac{28-5}{2} > 11$ and $2p \ge n-5 > n-7$.

Thus $n$ can be written as a sum of distinct primes such that the largest is at most $\max(7,n-7)$, and the induction holds as long as the claim is true for every $n$ from $7$ to $27$.

7 = 5+2
8 = 5+3
9 = 7+2
10 = 5+3+2
11 = 11
12 = 7+5
13 = 11+2
14 = 7+5+2
15 = 7+5+3
16 = 11+5
17 = 7+5+3+2
18 = 11+7
19 = 11+5+3
20 = 11+7+2
21 = 11+7+3
22 = 13+7+2
23 = 13+7+3
24 = 13+11
25 = 13+7+5
26 = 13+11+2
27 = 13+11+3

• Superb! I just corrected the line where you define $m$. Thanks! – Jeze Ken Aug 5 '15 at 20:40
• @JezeKen: Thanks! My silly careless mistake! – user21820 Aug 6 '15 at 0:28

Hint: Bertrand's postulate is useful for the inductive step. i.e. with the assumption this holds for all $n < M-1$, you have some prime $p$ s.t. $M \ge p > M/2$. Thus you can express $M-p$ as a sum of distinct primes, none of which are $p$.

All that remains is to show $n=7$ and that cases for which $M-p < 7$ can be handled. $M-p \in \{1, 4, 6\}$ will merit some detail... (times like this one wishes $1$ is allowed as a prime. This last part however seems to be quite difficult).

• You can use the stronger form giving a prime $k < p < 2k - 2$ for any $k \ge 4$. But you still have to consider $M - p \in \{4, 6\}$. – 6005 Aug 3 '15 at 4:47
• Thank you. I'm using your ideas, but do you think we can treat the cases $M-p=1,4,6$ without allowing the primes to be negative? – Jeze Ken Aug 3 '15 at 5:15
• I think for the approach given, it will be difficult. I think we will essentially have to find another large prime $p_2$ s.t. $M-p_2 > 6$ for those cases, and argue distinctiveness will hold with $p_2$. Will think about it more later. – Macavity Aug 3 '15 at 5:22
• Richert's theorem does use positive primes only. What you saw in the proof was that sums of the form $\sum_{k=1}^n\epsilon_kp_k$ with $\epsilon_k\in\{-1,1\}$ cover all integers (of correct parity) in a large interval. Adding $\sum_{k=1}^np_k$ produces all even numbers in a suitable interval where all coefficients are in $\{0,2\}$. Division by $2$ produces the claim. – Hagen von Eitzen Aug 3 '15 at 6:53
• The accepted answer to math.stackexchange.com/questions/1382803/… contains a short proof of Richert's result. – Hagen von Eitzen Aug 3 '15 at 9:37