Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose over $\mathbb{Z}$ we are given an irreducible polynomial $p(x)$.

Can we say that $p(x)$ at least represents a prime as $x$ runs through integers?

Thanks in advance

share|cite|improve this question
Have you seen this? – J. M. Jul 10 '12 at 14:27
I could be wrong but I think the question is..."Does every irreducible polynomial over $\mathbb{Z}$ represent at least one prime?" – fretty Jul 10 '12 at 17:03

No, e.g. irreducible $\rm\ f(x)\, =\, x(x+1)+4\ $ is even but $\rm\:f(x) \ne \pm 2.$

However, such fixed divisors of all values of $\rm\,f\,$ are essentially the only known obstruction to prime values. As motivation, let's start with a converse result. In $1918$ Stackel published the following simple observation:

Theorem If $\rm\, f(x)\,$ is a composite integer coefficient polynomial then $\rm\, f(n)\, $ is composite for all $\rm\,|n| > B,\, $ for some bound $\rm\,B.\,$ In fact $\rm\, f(n)\, $ has at most $\rm\, 2d\, $ prime values, where $\rm\, d = {\rm deg}(f)$.

The simple proof can be found online in Mott & Rose [3], p. 8. I highly recommend this delightful and stimulating $27$ page paper which discusses prime-producing polynomials and related topics.

Contrapositively, $\rm\, f(x)\, $ is prime (irreducible) if it assumes a prime value for large enough $\rm\, |x|\, $. As an example, Polya-Szego popularized A. Cohn's irreduciblity test, which states that $\rm\, f(x) \in \mathbb Z[x]\,$ is prime if $\rm\, f(b)\, $ yields a prime in radix $\rm\,b\,$ representation (so necessarily $\rm\,0 \le f_i < b).$

For example $\rm\,f(x) = x^4 + 6\, x^2 + 1 \pmod p\,$ factors for all primes $\rm\,p,\,$ yet $\rm\,f(x)\,$ is prime since $\rm\,f(8) = 10601\rm$ octal $= 4481$ is prime. Cohn's test fails if, in radix $\rm\,b,\,$ negative digits are allowed, e.g. $\rm\,f(x)\, =\, x^3 - 9 x^2 + x-9\, =\, (x-9)\,(x^2 + 1)\,$ but $\rm\,f(10) = 101\,$ is prime.

Conversely Bouniakowski conjectured $(1857)$ that prime $\rm\, f(x)\, $ assume infinitely many prime values (excluding cases where all the values of $\rm\,f\,$ have fixed common divisors, e.g. $\rm\, 2\: |\: x(x+1)+2\, ).$ However, except for linear polynomials (Dirichlet's theorem), this conjecture has never been proved for any polynomial of degree $> 1.$

Note that a result yielding the existence of one prime value extends to existence of infinitely many prime values, for any class of polynomials closed under shifts, viz. if $\rm\:f(n_1)\:$ is prime, then $\rm\:g(x) = f(x+ n_1\!+1)\:$ is prime for some $\rm\:x = n_2\in\Bbb N,\:$ etc.

For further detailed discussion of Bouniakowski's conjecture and related results, including heuristic and probabilistic arguments, see Chapter 6 of Ribenboim's The New Book of Prime Number Records.

[1] Bill Dubuque, sci.math 2002-11-12, On prime producing polynomials.

[2] Murty, Ram. Prime numbers and irreducible polynomials.
Amer. Math. Monthly, Vol. 109 (2002), no. 5, 452-458.

[3] Mott, Joe L.; Rose, Kermit. Prime producing cubic polynomials.
Ideal theoretic methods in commutative algebra, 281-317.
Lecture Notes in Pure and Appl. Math., 220, Dekker, New York, 2001.

share|cite|improve this answer

Let $P(x)$ be a polynomial of degree $\ge 1$, with integer coefficients, such that no $d \gt 1$ divides all the coefficients.

If $P(x)$ has degree $1$, then $P$ represents at least one prime. This is a consequence of Dirichlet's Theorem on primes in arithmetic progression (and easily implies that Theorem).

As has been pointed out, for degree $\ge 2$, irreducibility is not enough to ensure that a polynomial represents a prime. For some irreducible polynomials $P(x)$, there exists a $d \gt 1$ such that $d$ divides $P(n)$ for every integer $n$.

However, that can only happen for relatively simple congruential reasons. So let us focus attention on polynomials $P(x)$ for which there is no such universal $d$. Unfortunately, it is an open problem whether such a polynomial must necessarily represent at least one prime.

Example: There is a good deal of evidence that there are infinitely many primes of the form $x^2+1$. However, whether or not there are infinitely many is a long-standing open problem, often called the Hardy-Littlewood Conjecture. If we could show that for all $a\ne 0$, (or even infinitely many $a$) there exists $x$ such that $(2ax)^2+1$ is prime, that would settle the Hardy-Littlewood Conjecture. (Conversely, the Hardy-Littlewood Conjecture implies that there are infinitely many such $a$.)

So the question you raised seems to be extremely difficult even for polynomials of degree $2$!

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.