Number theoryDifficulty 5.9AIME, harderProve itSingapore
Determine the largest odd positive integer N such that every odd integer k with 1<k<N and (k,N)=1 is a prime.
Solution
The largest such integer N is 105. Let pi denote the ith prime, i.e. p1=2, p2=3, etc. We call a positive integer Nadmissible if it is odd and has the property stated in the problem. Any admissible number exceeding pi2 must clearly contain the factor pi for i≥2. By Bertrand's postulate, pn+1<2pn. Thus for any n≥5, we have pn+12<4pn2<8pn−1pn. Since p2p3=15>8, pn+12<p2p3⋯pn(n≥5)(1) If there were an admissible number N such that pn+12≥N>pn2 for some n≥5, then N would be divisible by p2p3⋯pn and so N≥p2p3⋯pn>pn+12 by (1) which gives a contradiction. Therefore no admissible number can exceed p52=121. The number 105 can be checked to be admissible. Also since any admissible number exceeding 49 must be divisible by 3×5×7=105, there can be no admissible number N between 105 and 121.
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.