Maths Olympiad Prep

Library / /14 of 27

Number theory Difficulty 8.1 Shortlist Prove it Saudi Arabia

Find all positive integers kk such that the product of the first kk primes increased by 1 is a power of an integer (with an exponent greater than 1).

Solution

Denote the first nn primes as
p1=2<p2=3<<pn p_1 = 2 < p_2 = 3 < \dots < p_n
Suppose that p1p2pn+1=xkp_1p_2\cdots p_n + 1 = x^k for some integers x,k2x, k \ge 2. We can assume WLOG that kk is prime since xkt=(xt)kx^{kt} = (x^t)^k. Obviously, xx has no prime factors not exceeding pnp_n, so x>pnx > p_n and consequently k<n<pnk < n < p_n is one of the first nn primes. Now xk1(modk)x^k \equiv 1 \pmod{k}, which implies x1(modk)x \equiv 1 \pmod{k}, but then by Lifting the Exponent Lemma
xk1(modk2). x^k \equiv 1 \pmod{k^2}.
This is a contradiction, as xk1=p1pnx^k - 1 = p_1 \cdots p_n is not divisible by the square of any prime. Thus, there does not exist any kk satisfying the problem. □

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 and solution reproduced as published; topic and difficulty added by this site.