# Thread: Partitioning integers into pairs so that the sum of each pair is prime.

1. ## Partitioning integers into pairs so that the sum of each pair is prime.

Show that, for every positive integer n, the numbers between 1 and 2n can be partitioned into pairs so that the sum of each pair is a prime number.

I tried a few examples, and I figured that an odd number must be paired up with an even number, which isn't much. You can split the numbers 1 to 2n into {1,3,...2n-1} and {2,4,...,2n}, and then somehow pick one number from each set such that all have prime sums, but I am kind of stuck.

2. Prove by induction.

The case $n=1$ is trivial.

Suppose that for $n = 1,2,\dots,m-1$, the integers $1,2,\dots,2n-1,2n$ can be partitioned in pairs $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$ s.t. $\forall j, x_j+y_j = prime.$

For $n=m$, we have the integers $1,2,\dots,2m-1,2m$. By the Bertrand-Chebyshev theorem $\exists p=prime$ s.t. $2m. Therefore we have the following pairs:

$(p-2m,2m), (p-2m+1,2m-1),\dots, ((p-1)/2,(p+1)/2)$.

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