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

Is there a generalization of Dirichlet's theorem along these lines?

If $p(n)$ is a polynomial of degree $k$ with positive integers as coefficients, such that the coefficients are relatively prime, then the sequence $p(1),p(2),p(3),\ldots$ has infinitely many primes?

$k=1$ is the good old Dirichlet's theorem on arithmetic progressions.

If the above is false, is there a trivial example for some degree '$k$'?

share|cite|improve this question
up vote 12 down vote accepted

This is false as stated. Take, for example, $p(n) = n^2 + n$. The correct condition is that $p$ is irreducible and there exists no $d > 1$ such that $d | p(n)$ for all $n$. With this condition this is a big open problem, the Bunyakovsky conjecture, and it is open for any such polynomial $p$ of degree greater than $1$.

share|cite|improve this answer
Thanks. That was helpful. (Though $n^2 + 4n + 3$ would have been a better example since my question want all the coefficients including the constant term to be positive) It makes sense to talk of irreducible polynomials as opposed to polynomials with relatively prime coefficients. – user17762 May 30 '11 at 19:04

In 1918 Stackel published the following simple observation:

THEOREM If $ p(x)$ is a composite integer coefficient polynomial

then $ p(n) $ is composite for all $|n| > B $, for some bound $B$,

in fact $ p(n) $ has at most $ 2d $ prime values, where $ d = {\rm deg}(p)$.

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, $ p(x) $ is prime (irreducible) if it assumes a prime value for large enough $ |x| $. Conversely Bouniakowski conjectured (1857) that prime $ p(x) $ assume infinitely many prime values (except in trivial cases where the values of $p$ have an obvious common divisor, e.g. $ 2 | x(x+1)+2$ ).

As an example, Polya-Szego popularized A. Cohn's irreduciblity test, which states that $ p(x) \in {\mathbb Z}[x]$ is prime if $ p(b) $ yields a prime in radix $b$ representation (so necessarily $0 \le p_i < b$).

For example $f(x) = x^4 + 6 x^2 + 1 \pmod p$ factors for all primes $p$, yet $f(x)$ is prime since $f(8) = 10601$ octal $= 4481$ is prime.

Note: Cohn's test fails if, in radix $b$, negative digits are allowed, e.g. $f(x) = x^3 - 9 x^2 + x-9 = (x-9)(x^2 + 1)$ but $f(10) = 101$ is prime.

For further discussion see my prior post [1], along with Murty's online paper [2].

[1] 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
Thanks Bill. I am unable to open the article by Mott, Joe L.; Rose, Kermit – user17762 May 30 '11 at 19:09
@Sivaram It's now a gzipped postscript file, so you'll need a decompression program that handles gzip, and a postscript viewer (e.g. GSView). – Bill Dubuque May 30 '11 at 19:12

It is conjectured there are infinitely many primes of the form $n^2 + 1$ but not proven.

share|cite|improve this answer

Your Answer


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