## Task 4.

Determine all natural numbers $n \geqslant 3$ for which the product of the first $n$ natural numbers divides the product of all sums of distinct pairs of prime numbers not greater than $n$, i.e., for which

$$
n! \mid \prod_{\substack{p<q \leqslant n \\ p, q \text{ prime }}}(p+q)
$$
## Solution.

Notice that 3, 4, 5, and 6 are not solutions to the problem because in these cases, the left side is divisible by 3, while the right side is not. Furthermore, for $n=7$, the left side is equal to $2^{4} \cdot 3^{2} \cdot 5 \cdot 7$, and the right side is $5 \cdot 7 \cdot 9 \cdot 8 \cdot 10 \cdot 12 = 7 \cdot 5 \cdot 3^{3} \cdot 2^{6}$, so 7 is a solution to the problem. For $n \in \{8,9,10\}$, the left side is divisible by $2^{7}$, while the right side is not, so these numbers are not solutions to the problem.

Assume that some $n \geqslant 11$ is a solution to the problem. Consider the largest prime number $r \leqslant n$. Then $r \mid n!$, so $r \mid p+q$ for some pair of prime numbers $p, q$ that are less than $n$. However, then $p<q \leqslant r$, so $p+q<2r$, which means $p+q=r$. Due to the parity, this is only possible for $p=2$ and $q=r-2$. We conclude that $r-2$ is also prime.

Then $r-2 \mid n!$, so $r-2$ must divide $p+q$ for some pair of prime numbers with $p<q \leqslant r$.

If $q=r$, then $r-2 \mid p+r$, which means $r-2 \mid p+2$, so $p \geqslant r-4$.

It cannot be $p=r-2$ because $r-2 \nmid 2r-2$, and it cannot be $p=r-1$ or $p=r-3$ due to parity, so $p=r-4$ and we conclude that $r-4$ is also prime.

If $q<r$, then $q \leqslant r-2$, $p<r-2$, so $p+q<2(r-2)$, so it must be $p+q=r-2$. As before, we conclude $p=2$ and $q=r-4$, so $r-4$ is also prime in this case.

Thus, $r, r-2, r-4$ are prime numbers. However, they give different remainders when divided by 3, so one of them is divisible by 3, so one of them is equal to 3. But this is impossible because $r \geqslant 11$.

Therefore, $n=7$ is the only solution.

## CROATIAN MATHEMATICAL OLYMPIAD

## Final test for selecting the MEMO team

Zagreb, May 24, 2023.