Maths Olympiad Prep

Library / /36 of 56

Number theory Difficulty 5.9 AIME, harder Prove it Singapore

Determine the largest odd positive integer NN such that every odd integer kk with 1<k<N1 < k < N and (k,N)=1(k, N) = 1 is a prime.

Solution

The largest such integer NN is 105105. Let pip_i denote the iith prime, i.e. p1=2p_1 = 2, p2=3p_2 = 3, etc. We call a positive integer NN admissible if it is odd and has the property stated in the problem. Any admissible number exceeding pi2p_i^2 must clearly contain the factor pip_i for i2i \ge 2. By Bertrand's postulate, pn+1<2pnp_{n+1} < 2p_n. Thus for any n5n \ge 5, we have pn+12<4pn2<8pn1pnp_{n+1}^2 < 4p_n^2 < 8p_{n-1}p_n. Since p2p3=15>8p_2p_3 = 15 > 8,
pn+12<p2p3pn(n5)(1) p_{n+1}^2 < p_2 p_3 \cdots p_n \quad (n \ge 5) \qquad (1)
If there were an admissible number NN such that pn+12N>pn2p_{n+1}^2 \ge N > p_n^2 for some n5n \ge 5, then NN would be divisible by p2p3pnp_2p_3 \cdots p_n and so Np2p3pn>pn+12N \ge p_2p_3 \cdots p_n > p_{n+1}^2 by (1) which gives a contradiction. Therefore no admissible number can exceed p52=121p_5^2 = 121.
The number 105105 can be checked to be admissible. Also since any admissible number exceeding 4949 must be divisible by 3×5×7=1053 \times 5 \times 7 = 105, there can be no admissible number NN between 105105 and 121121.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.