Maths Olympiad Prep

Library / /254 of 397

, 2023

Number theory Difficulty 6.2 National Olympiad Prove it Taiwan

Find all positive integers n3n \ge 3 such that
n!p<qn,p,q primes(p+q). n! \prod_{\substack{p<q \le n, \\ p,q \text{ primes}}} (p+q).
That is, n!n! divides the product p<qn, p,q primes(p+q)\prod_{p<q \le n,\ p,q\ \text{primes}} (p+q).

Solution

This only holds for n=7n = 7.

Let 2=p1<p2<<pmn2 = p_1 < p_2 < \cdots < p_m \le n be the primes n\le n. Each such prime divides n!n!.

In particular, pmpi+pjp_m \mid p_i + p_j for some pi<pjnp_i < p_j \le n. But
0<pi+pjpm<2, 0 < \frac{p_i + p_j}{p_m} < 2,
so pm=pi+pjp_m = p_i + p_j which implies m3m \ge 3, pi=2p_i = 2, and pm=2+pj=2+pm1p_m = 2 + p_j = 2 + p_{m-1}.

Similarly, pm1pk+plp_{m-1} \mid p_k + p_l for some pk<plnp_k < p_l \le n. But
0<pl+pkpm1<3. 0 < \frac{p_l + p_k}{p_{m-1}} < 3.
Thus, it is easy to check that we must have pm1=pm2+2p_{m-1} = p_{m-2} + 2.

Hence, one of pm2,pm1,pmp_{m-2}, p_{m-1}, p_m is divided by 33. Easy to check that pm2=3p_{m-2} = 3 is the only possible case, i.e., p1,p2,,pm=2,3,5,7p_1, p_2, \cdots, p_m = 2, 3, 5, 7 and
i<j(pi+pj)=57981012=7!60 \prod_{i<j} (p_i + p_j) = 5 \cdot 7 \cdot 9 \cdot 8 \cdot 10 \cdot 12 = 7! \cdot 60
So the condition only holds for n=7n = 7.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from en; metadata (topic, difficulty) added by this project.