A polynomial formula for the primes

114 Views Asked by At

Is there a proof that there is no polynomial which would return $n$th prime for the input value $n$?

In other words is there an explanation for why there is no polynomial $P(x)$ such that $P(n)=p_n$ for every natural number $n$ and $p_n$ being the $n$th prime and the coefficients of the polynomial being taken from some field.

2

There are 2 best solutions below

0
On

Let $F$ be a field which contains the rationals, and let $P$ be a non-constant polynomial with coefficients in $F$ such that $P(n)$ takes on prime values for infinitely many positive integers $n$. We show that $P(n)$ also takes on non-prime values.

For suppose that $P$ is prime for infinitely many positive $n$, and has degree $m\ge 1$. The coefficients of $P$ are rational. For suppose $P(a_i)=b_i$, where the $a_i$ and $b_i$ are rational, for $m+1$ distinct $a_i$. By Lagrange interpolation, there is a polynomial $P^\ast$ with rational coefficients and degree $\le m$ such that $P^\ast(a_i)=P(a_i)$ at our $m+1$ distinct $a_i$. But then by uniqueness $P=P^\ast$.

There is an integer $L\ge 1$ such that all the coefficients of $P$ have shape $\frac{p_i}{L}$, where the $p_i$ are integers. Then $P(x)=\frac{Q(x)}{L}$ where $Q(x)$ has integer coefficients.

Suppose that $P(n_0)=p$. Then $Q(n_0)=Lp$. For any $k$, we have $Q(n_0+Lpk)$ is divisible by $Lp$. So $P(n_0+Lpk)$ is an integer divisible by $p$. It follows that for any large enough $k$, the number $P(n_0+Lpk)$ cannot be prime.

1
On

Say $p(x)$ does as you want. Then $p(0) = q$, a prime. But each term of $p(q x)$ is divisible by $q$, and so $q$ divides $p(q x)$, which is a prime. Thus $p(q x) = q$ for all $x \in \mathbb{N}$, contradiction.