Let be an integer. A positive integer is called -able if we can partition the numbers into two sets and such that the sum of the elements of is exactly times the sum of the elements of . Prove that the smallest -able number is relatively prime to .
Solution
We will prove that if is the smallest prime divisor of , then is the smallest -pable number. This implies the desired result, as it then follows that . We know that . If is a -pable number and is the sum of the elements in , then the sum of the elements in is , so the total sum is and this must equal . Thus, . Since , it follows that , where is the smallest prime divisor of . Therefore, . We will now prove that is a -pable number, which immediately implies that it is the smallest -pable number. And we are done, because since there are no prime divisors smaller than in .
First, assume that is even, so . We need to prove that we can partition the set into two sets with equal sums of the elements. We prove this by induction on . For and , we have and , respectively. If we can partition the set in this way, we can also do it for the set by placing the new elements into the sets such that and go into one set and and go into the other. This completes the induction. Now assume that is odd. Write . It is sufficient to find a subset of whose sum of elements is , because then the sum of the elements in the set is , which is exactly times the sum of the elements in . Consider the set . Then the sum of the elements in is
exactly as intended.