a. Does there exist 4 distinct positive integers such that the sum of any 3 of them is prime? b. Does there exist 5 distinct positive integers such that the sum of any 3 of them is prime?
Problem
Source: Indonesia TST 2009 First Stage Test 3 Problem 1
Tags: pigeonhole principle, search, number theory proposed, number theory
01.01.2009 18:36
a) Yes, for example $ \{1,5,7,11\}$, since $ 1+5+7=13$, $ 1+5+11=17$, $ 1+7+11=19$ and $ 5+7+11=23$. b) No, because if there are three of them that are equal mod 3, they sum to $ 0\bmod{3}$, so that sum can't be a prime. Also, we can't have three that are pairwise distinct mod 3, since $ 0+1+2\equiv 0\bmod{3}$. So by pigeonhole we can have at most $ 2\times2=4$ numbers, as desired.
01.01.2009 18:39
Again, the general form of b) is: In any $ 2n - 1$ integers, we can find $ n$ such that their sum is divisible by $ n$. Search for Erdös-Ginzburg-Ziv if you want.
31.05.2010 11:31
a) yes, for example $\{3,3,5,5\}$
31.05.2010 11:35
oh ,sorry I don't see that there is the positive integers are distnic!
31.05.2010 11:58
hi, a)yes, the examples are in file!
31.05.2010 12:00
I try to upload a file but can't it says "the extension out is not allowed", example is $\{1,3,7,9\}$
11.05.2011 20:13
a) example: $3,7,9,19$ b) if look at remainders modulo 3. If we have $0,1,2$, we have a number divisible by 3 which can't be prime. So we have only $2$ remainders(if we have only one, then every sum of 3 numbers is multiple of 3). Using pigeonhole's principle we have 3 numbers given the samen remainder modulo 3, so their sum is multiple of 3, so it is not prime($1+1+1=3$ is the only such pair, but they are not distinct)
30.10.2011 07:36
for a,it suffices to consider 1,3,7,9.
30.10.2011 07:38
moreover,do there exist infinite number of pairs of such quadruples?
22.12.2014 22:08
Related:What is the maximal $n$ such that there are $n$ integers (possibly negative) satisfying that condition(the sum of every three numbers is a prime number)?