5
$\begingroup$

Here is a nice high school olympiad math problem:

Can you choose 4 distinct positive integers so that the sum of each 3 of them is prime? How about 5?

It looks that just by looking at reminders mod 2,3,6 is not enough.

$\endgroup$
8
$\begingroup$

One important issue to consider in choosing the $4$ integers is the parity. For the sum of each of them to be prime means that you must have $2$ or less being even as the sum of $3$ even numbers is even. If you have $2$ or $1$ even (and $2$ or $3$ odd) numbers, then choosing $1$ even and $2$ odd numbers makes the sum even. Thus, you need to have all $4$ numbers being odd.

Considering remainders modulo $3$, note if $3$ or $4$ of the numbers have the same remainder, the sum of $3$ of them would be a multiple of $3$ and, thus, not prime. As such, you need to have $2$ groups of $2$ different remainders modulo $3$.

One set which meets these requirements is $\{1,3,7,9\}$ giving sums, when taken $3$ at a time, of $11,13,17,19$. In this case, there are $2$ numbers each with a remainder of $0$ and $1$ modulo $3$.

For $5$ (or more) integers, once again, you can't have $3$ or more with the same remainder modulo $3$. However, with at most $2$ having any the same remainders modulo $3$, there must be at least one integer each with a remainder of $0, 1$ and $2$, so the sum of those $3$ would, once again, be a multiple of $3$, so it's not a prime. Thus, you can't have $5$ or more such integers where the sum of each subset of $3$ is a prime.

FYI, this property that a set of $5$ integers always has a subset of $3$ that sum to a multiple of $3$ is an example of the more general case of, for all $n \in \mathbb{N}$, that a set of $2n - 1$ integers always has at least one of subset of $n$ integers which sum to a multiple of $n$. For larger specific cases, there's Given 7 arbitrary integers,sum of 4 of them is divisible by 4 and Among any $11$ integers, sum of $6$ of them is divisible by $6$. At a math seminar I attended just under $40$ years ago, we were told the general case was not yet proven. I just did a brief online search but could not find whether or not this is still the case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.