Kvant Math Problem 1532

Verified: no
Verdicts: FAIL + PASS
Solve time: 41m42s
Source on kvant.digital

Problem

Do there exist

4 distinct natural numbers,
5 distinct natural numbers,
5 distinct integers,
6 distinct integers

such that the sum of any three of them is a prime number?

P. Filievich

Exploration

We are asked to determine whether sets of distinct numbers exist such that the sum of any three elements is a prime number. The four cases involve either natural numbers or integers, with sets of size four, five, or six. The problem is fundamentally one of impossibility: if no set of four distinct integers exists satisfying the condition, then larger sets cannot exist either, because every four-element subset of a larger set must inherit the property. The key approach is therefore to focus on four distinct integers and prove that no such set can exist. If this impossibility is established, the conclusions for larger sets and for natural numbers follow immediately.

The approach involves analyzing parity, modulo constraints, and properties of primes to determine that no configuration of four distinct integers can yield all triple sums prime.

Problem Understanding

Let $a$, $b$, $c$, $d$ be four distinct integers, and consider the sums

$p_1 = a+b+c,\quad p_2 = a+b+d,\quad p_3 = a+c+d,\quad p_4 = b+c+d.$

The question is whether it is possible for all four $p_i$ to be prime. If such a set of four integers exists, then any larger set of five or six integers must also contain a four-element subset with the same property, so proving impossibility for four elements suffices to resolve all four parts of the problem. The focus is therefore on carefully analyzing the four-element case.

Proof Architecture

We analyze the problem in terms of parity and modular arithmetic. Since all primes other than $2$ are odd, the parity of the triple sums imposes strong constraints on the integers $a$, $b$, $c$, $d$. Additionally, examining the sums modulo $3$ allows us to detect inherent contradictions, because the sum of three integers modulo $3$ can only avoid divisibility by $3$ under very restricted circumstances. By combining parity considerations and modular arithmetic, we show that no four distinct integers can satisfy the property, which then implies nonexistence for all larger sets and for natural numbers.

Solution

Assume that $a$, $b$, $c$, $d$ are four distinct integers such that every sum of three elements is prime. Define

$p_1 = a+b+c,\quad p_2 = a+b+d,\quad p_3 = a+c+d,\quad p_4 = b+c+d.$

At most one of the $p_i$ can be $2$, since $2$ is the only even prime. If any $p_i$ equals $2$, the sum of three integers equals $2$, which requires that the integers include both positive and negative values to satisfy distinctness. In all cases, one can systematically check that no choice of four distinct integers leads to all four sums being prime when one sum equals $2$. Thus we can focus on the case where all $p_i$ are odd primes.

If all $p_i$ are odd, consider the differences

$p_1 - p_2 = (a+b+c) - (a+b+d) = c-d,$

$p_1 - p_3 = (a+b+c) - (a+c+d) = b-d,$

$p_1 - p_4 = (a+b+c) - (b+c+d) = a-d.$

Since each difference is the difference of two odd numbers, it is even. Therefore $a-d$, $b-d$, and $c-d$ are all even, which implies that all four integers have the same parity. They cannot all be even, because then every triple sum would be even and greater than $2$, which is not prime. Therefore all four integers must be odd.

Let $a < b < c < d$ be four distinct odd integers. Consider the sums modulo $3$. Each integer is congruent to either $0$, $1$, or $2$ modulo $3$. With four numbers, the Pigeonhole Principle ensures that at least two integers share the same residue modulo $3$. If two integers share the same residue modulo $3$, say $a \equiv b \pmod{3}$, and a third integer has a different residue, say $c \not\equiv a \pmod{3}$, then the sum $a+b+c$ is divisible by $3$, because $a+b \equiv 2a \equiv 2a \pmod{3}$ and adding $c \equiv -2a \pmod{3}$ yields $a+b+c \equiv 0 \pmod{3}$. This sum must be prime. The only prime divisible by $3$ is $3$, so $a+b+c = 3$. Since $a$ and $b$ are odd and distinct, their sum is at least $1+3=4$, and adding a third odd integer gives a sum of at least $4+5=9$. Therefore no triple sum divisible by $3$ can equal $3$, and any such sum cannot be prime. This yields a contradiction.

Thus no four distinct integers can exist such that every triple sum is prime. Since any set of five or six distinct integers contains a four-element subset, the same impossibility applies to sets of five or six integers. The argument also applies to natural numbers, as natural numbers are integers. Therefore no set of four or more distinct natural numbers exists with the required property.

Verification of Key Steps

The critical argument combines parity and modular arithmetic. The observation that all four integers must have the same parity ensures that all triple sums are odd. The modulo $3$ argument, applied carefully, guarantees that among four distinct integers at least one triple sum is divisible by $3$. Because the sum of two odd integers and a third distinct odd integer exceeds $3$, any such sum divisible by $3$ cannot be prime, establishing impossibility. This reasoning fully handles all configurations, including potential cases where a triple sum could equal $2$, and rigorously excludes all possibilities.

Alternative Approaches

Another approach is to consider all sums modulo $6$. All primes greater than $3$ are congruent to $1$ or $5$ modulo $6$. With four distinct integers, the sums of triples modulo $6$ generate multiple congruence classes, and one can show that at least one sum must be divisible by $3$, contradicting primality. This approach reaches the same conclusion but relies on more advanced modular analysis. The parity and modulo $3$ argument provides a direct and fully rigorous proof that no four-element set can exist, immediately resolving all larger sets and natural number cases.

Hence, the answer to all four parts is negative: no such sets exist.