Maths Olympiad Prep

Library / Saudi Arabian IMO Booklet /13 of 26

Saudi Arabian IMO Booklet

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 p1p2⋯pn+1=xkp_1p_2\cdots p_n + 1 = x^k for some integers x,k≥2x, 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 xk≡1(modk)x^k \equiv 1 \pmod{k}, which implies x≡1(modk)x \equiv 1 \pmod{k}, but then by Lifting the Exponent Lemma
xk≡1(modk2). x^k \equiv 1 \pmod{k^2}.
This is a contradiction, as xk−1=p1⋯pnx^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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.