The prime numbers are defined in terms of the multiplicative structure of the natural numbers, \(\mathbf{N}\). Specifically, the definition of prime–that \(p \in \mathbf{N}\) is prime if it has no non-trivial divisors–only refers to multiplication, not addition. The *additive* structure of the prime numbers is much less well understood, and indeed, many of the most famous open problems and deepest theorems in number theory concern the additive structure of the primes. For example, see the twin primes conjecture, the Goldbach conjecture, the abc conjecture, and the Green-Tao theorem. In this post, we consider a much weaker variant of the Goldbach Conjecture:

Theorem 1. Every natural number \(m\) with \(1 Bertrand’s Postulate.

Bertrand’s Postulate. For every natural number \(m > 1\) there exists a prime \(p\) satisfying \(m (m – 1) / 2\). Thus, \(m_1 = m – p_1 \leq m / 2\). Since each iteration of our procedure for finding \(p_1, \ldots, p_k\) cuts the size of the problem in half, the process should terminate after \(\log_2 m\) iterations. We are now ready to formalize this intuition with a proof.

Proof of Theorem 1. We argue by induction on \(n\). For the base case, \(n = 1\), the only natural numbers \(m\) with \(1 1\). We will show that Theorem 1 also holds for \(n+1\). Suppose \(m\) satisfies \(1 (m – 1) / 2\), thus \(m_1 = m – p_1\) satisfies \(m_1