Maths WorkshopMaths problems with full solutions
Exercise 1292Algebra › PolynomialsM1Added 5 Nov 2026

No polynomial takes only prime values

#integer polynomials#primes#divisibility#congruences

Statement

Let PP be a non-constant polynomial with integer coefficients. Prove that there are infinitely many integers nn for which ∣P(n)∣|P(n)| is not a prime number.

Hint

Take n0n_0 with m=P(n0)m=P(n_0) and ∣m∣≥2|m|\ge2. For which kk is P(n0+km)P(n_0+km) divisible by mm? Why can P(n0+km)P(n_0+km) not equal ±m\pm m for most kk?

Show solutionHide solution

Solution

A value of absolute value at least 22. A non-constant polynomial is unbounded, so there is an integer n0n_0 with ∣P(n0)∣≥2|P(n_0)|\ge2. Put m=P(n0)m=P(n_0).

Divisibility. For integer polynomials, a−b∣P(a)−P(b)a-b\mid P(a)-P(b). With a=n0+kma=n_0+km, b=n0b=n_0 we get m∣P(n0+km)−mm\mid P(n_0+km)-m, so m∣P(n0+km)m\mid P(n_0+km) for every integer kk.

Large values. A non-constant polynomial takes each value at most deg⁡P\deg P times, so for all but finitely many kk, P(n0+km)∉{m,−m}P(n_0+km)\notin\{m,-m\}. Taking also ∣n0+km∣|n_0+km| large enough that ∣P(n0+km)∣>∣m∣|P(n_0+km)|>|m|, we get a multiple of mm whose absolute value is strictly larger than ∣m∣≥2|m|\ge2.

Conclusion. Such a number ∣P(n0+km)∣|P(n_0+km)| has the divisor ∣m∣|m| with 1<∣m∣<∣P(n0+km)∣1<|m|<|P(n_0+km)|, so it is composite. This happens for infinitely many kk, giving infinitely many integers n=n0+kmn=n_0+km. ■\blacksquare

Remark. Famous examples such as n2+n+41n^2+n+41 are prime for many consecutive nn (here n=0,…,39n=0,\dots,39), but must fail eventually (at n=41n=41, P(41)=41⋅43P(41)=41\cdot43).

Lesson. The congruence a−b∣P(a)−P(b)a-b\mid P(a)-P(b) lets you make a polynomial value divisible by a number you control.