Maths Olympiad Prep

Library / /106 of 520

Number theory Difficulty 5.8 AIME, harder Prove it

30. (SWE 2) IMO5{ }^{\mathrm{IMO} 5} For which positive integers nn does there exist a positive integer NN such that none of the integers 1+N,2+N,,n+N1+N, 2+N, \ldots, n+N is the power of a prime number?

Solution

30. For all nn such NN exists. For a given nn choose N=(n+1)!2+1N=(n+1)!^{2}+1. Then 1+j1+j is a proper factor of N+jN+j for 1jn1 \leq j \leq n. So if N+j=pmN+j=p^{m} is a power of a prime pp, then 1+j=pr1+j=p^{r} for some integer r,1r<mr, 1 \leq r<m. But then pr+1p^{r+1} divides both (n+1)!2=N1(n+1)!^{2}=N-1 and pm=N+jp^{m}=N+j, implying that pr+11+jp^{r+1} \mid 1+j, which is impossible. Thus none of N+1,N+2,,N+nN+1, N+2, \ldots, N+n is a power of a prime. Second solution. Let p1,p2,,p2np_{1}, p_{2}, \ldots, p_{2 n} be distinct primes. By the Chinese remainder theorem, there exists a natural number NN such that p1p2N+1,p3p4N+2,,p2n1p2nN+np_{1} p_{2} \mid N+1, p_{3} p_{4} \mid N+2, \ldots, p_{2 n-1} p_{2 n} \mid N+n, and then obviously none of the numbers N+1,,N+nN+1, \ldots, N+n can be a power of a prime.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.