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

**comssa** · December 7th 2009, 02:56 PM

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.

**Black** · December 7th 2009, 05:54 PM

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<p<4m \Longrightarrow p-2m<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.

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

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

Using the fact that a pair of numbers is relatively prime to prove that one is prime

Proving a pair of integers are not prime in a particular number system

Find a pair of integers

number of pair of integers (x,y) satisying an equation

[SOLVED] Pairs of integers that add up to 7 (and 17)

Search Tags