IMO 1989 SL 30

Origin: SWE

Problem

For which positive integers n does there exist a positive integer N such that none of the integers 1 + N, 2 + N, . . . , n + N is the power of a prime number?

Solution

For all n such N exists. For a given n choose N = (n + 1)!2 + 1. Then 1 + j is a proper factor of N + j for 1 \leqj \leqn. So if N + j = pm is a power of a prime p, then 1 + j = pr for some integer r, 1 \leqr < m. But then pr+1 divides both (n + 1)!2 = N −1 and pm = N + j, implying that pr+1 | 1 + j, which is impossible. Thus none of N + 1, N + 2, . . . , N + n is a power of a prime. Second solution. Let p1, p2, . . . , p2n be distinct primes. By the Chinese remainder theorem, there exists a natural number N such that p1p2 | N + 1, p3p4 | N + 2, . . . , p2n−1p2n | N + n, and then obviously none of the numbers N + 1, . . . , N + n can be a power of a prime.