Prove by induction.

The case is trivial.

Suppose that for , the integers can be partitioned in pairs s.t.

For , we have the integers . By the Bertrand-Chebyshev theorem s.t..Therefore we have the following pairs:

.

This takes care of the integers to . For the rest, note that is an even number (odd-odd=even) and . By the induction hypothesis, we can partition the remaining integers into pairs s.t. the sum of each pair is prime. Q.E.D.