# 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 $\displaystyle n=1$ is trivial.

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

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

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

This takes care of the integers $\displaystyle p-2m$ to $\displaystyle 2m$. For the rest, note that $\displaystyle p-2m-1$ is an even number (odd-odd=even) and $\displaystyle 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.