MathOverflow is a question and answer site for professional mathematicians. 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

Let $f(n)=a_3n^3+a_2n^2+a_1n+a_0$, with $a_i\in\mathbb{Z}$, $a_3>0, a_0\neq 0$ such that $f(n)>0$ for all positive integers $n$.

Given a prime $p$, when is $f(p)$ again prime?

For example, let $f(n)=7n^3-50n+30$. Then, $$f(7)=2081\quad {\rm (prime)},$$ $$f(11)=19\cdot463,$$ $$f(13)=14759\quad {\rm (prime)}.$$

Are there conditions on the $a_i$'s that guarantee that $f(p)$ is prime for all primes $p$?

share|cite|improve this question
It is not known for any polynomial $f$ of degree greater than 1 whether $f(n)$ is prime for infinitely many values of $n$, prime or otherwise. This is the Buniakowsky conjecture (when $f$ satisfies the obvious necessary condition). – Qiaochu Yuan May 5 '11 at 2:23
Qiaochu: the "obvious" necessary conditions are not all obvious. On first glance most people would agree that the obvious necessary conditions are that f(x) is irreducible, its leading coeff. is positive, and its coefficients as a polynomial have no common factors. But that last condition is not adequate and the substitute for it, I would say, is somewhat subtle (albeit elementary). – KConrad May 5 '11 at 4:35
Jeff, You can use Bateman-Horn heuristics to estimate $\left|\{f(p): p \leq x, f(p) \mbox{ is prime}\}\right|$. Use Bateman-Horn for two polynomials, set $f_1(n)=n$ and $f_2(n)=f(n)$, the cubic polynomial you want. Bateman-Horn will count the inputs $n \leq x$ for which both are prime. – Timothy Foo Oct 22 '11 at 4:31
up vote 16 down vote accepted

There is no non-constant polynomial sending primes to primes, aside from $f(x)=x$. Indeed, it suffices to consider the case where $f$ is irreducible, as if $f(x)$ factors as $g(x)h(x)$, $f(p)$ is clearly composite for large $p$.

Now if $f(x)\not=x$, choose some large prime $p$ such that $f$ has a non-zero root $a$ in $\mathbb{F}_p$. By Dirichlet's theorem on primes in arithmetic progressions, there exist infinitely many primes $q_i$ with $q_i\equiv a\bmod p$. But for such $q_i$, $f(q_i)$ is divisible by $p$, and thus taking $q_i$ large, we have that $f(q_i)$ is composite.

I've been a bit glib about why one can choose $p$ as claimed; just look for primes which split in the splitting field of $f$ over $\mathbb{Q}$.

EDIT: More simply, use Lemma 1 here to pick $p$.

share|cite|improve this answer
(I guess this is an answer to your last question, about what conditions on $f$ guarantee $f(p)$ prime for all primes $p$. The other, as Qiaochu points out, is wildly open, but the condition is conjectured to be the irreducibility of $f$.) – Daniel Litt May 5 '11 at 2:42
Also I guess I'm using Chebotarev to pick a prime that splits. – Daniel Litt May 5 '11 at 2:54
Daniel: irreducibility is not enough, e.g., x^2 - x + 2 is irreducible but has a hard time taking prime values. Also, while Chebotarev is a simple way to think about why there are lots of primes that split completely in a number field, that particular corollary of Chebotarev can be proved in about one page by a very elementary argument along the lines of Euclid's proof that there are infinitely many primes. See a paper by Cassels which I refer to in a common to Bjorn's answer at… – KConrad May 5 '11 at 4:50
+1: You're right of course. Bjorn's proof is very nice as well. – Daniel Litt May 5 '11 at 5:32
(The added condition should be--the gcd of the integer values of $f$ must be $1$; e.g. $f$ must not vanish identically mod any prime. The example KConrad gives vanishes mod $2$.) – Daniel Litt May 5 '11 at 5:36

It is, I think, better to investigate the last coefficient a0. It is easy to show that a0 cannot have more than 3 distinct prime factors. because, suppose that p is a prime factor of a0. then, if f(p) is prime, it must be = p, since p divides f(p). similar are the cases for other prime factors of a0. in short, if t is a prime factor of a0, then f(t)= t. but f being a cubic, it can't have more than three zeroes. this leads to my 1st statement. obviously irreducibility and all that are necessary conditions. i think a little more effort can solve your last problem.

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.