Maths Olympiad Prep

Library / Taiwan IMO Selection Camp /234 of 359

Taiwan IMO Selection Camp, 2023

Number theory Difficulty 6.2 National Olympiad Prove it Taiwan

Find all positive integers n≥3n \ge 3 such that
n!∏p<q≤n,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<q≤n, 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<⋯<pm≤n2 = p_1 < p_2 < \cdots < p_m \le n be the primes ≤n\le n. Each such prime divides n!n!.

In particular, pm∣pi+pjp_m \mid p_i + p_j for some pi<pj≤np_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 m≥3m \ge 3, pi=2p_i = 2, and pm=2+pj=2+pm−1p_m = 2 + p_j = 2 + p_{m-1}.

Similarly, pm−1∣pk+plp_{m-1} \mid p_k + p_l for some pk<pl≤np_k < p_l \le n. But
0<pl+pkpm−1<3. 0 < \frac{p_l + p_k}{p_{m-1}} < 3.
Thus, it is easy to check that we must have pm−1=pm−2+2p_{m-1} = p_{m-2} + 2.

Hence, one of pm−2,pm−1,pmp_{m-2}, p_{m-1}, p_m is divided by 33. Easy to check that pm−2=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)=5⋅7⋅9⋅8⋅10⋅12=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,604 problems in a working order, from Junior Challenge 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.