È ben noto che esistono polinomi p(x) a coefficienti interi che assumono valori primi per numerosi valori interi consecutivi di x. Ad esempio, x²−x+41 è primo per ogni 1 ≤ x ≤ 40, e x²−79x+1601 è primo per ogni 1 ≤ x ≤ 79.

Tuttavia, non è possibile che un polinomio a coefficienti interi assuma esclusivamente valori primi, come mostra il seguente elegante argomento [1, Theorem 21 p. 22].

Sia f(x)= a₀xᵏ +… un polinomio a coefficienti interi. Possiamo assumere a₀>0, in modo che lim f(x)=+∞ quando x → +∞. In particolare, f(x)>1 per x sufficientemente grande.

Fissiamo un intero positivo n tale che f(n)>1, e poniamo m=f(n).

Se r è un intero positivo arbitrario, allora la quantità

f(rm+n) = a₀(rm+n)ᵏ + … = m(...)+f(n) = m(...) + m

è divisibile per m qualunque sia r. Quindi f(rm+n) è composto e, siccome rm+n diventa arbitrariamente grande al crescere di r, deduciamo che f(x) è composto per infiniti valori interi di x.

OSSERVAZIONE. Ogni polinomio lineare irriducibile su Z rappresenta infiniti numeri primi per il teorema di Dirichlet. Non è noto se esistano polinomi di grado >1 che rappresentano infiniti primi.

D'altra parte, non è difficile esibire polinomi irriducibili su Z che non rappresentano neanche un numero primo. Un esempio è

f(x)=x(x+1)+4

che rappresenta solo numeri pari, e non rappresenta ±2.