Thread: A polynomial that is always prime?

1. A polynomial that is always prime?

Does there exist an f(x) minimum first-degree polynomial with integer coefficients, such that for any x integer number, f(x) is prime?

Any help would be appreciated!

2. Originally Posted by doug
Does there exist an f(x) minimum first-degree polynomial with integer coefficients, such that for any x integer number, f(x) is prime?

Any help would be appreciated!
No!
Proof by reductio ad impossibile.
Suppose that there is exist such polynomial $f(n)$.

$f(n)=a_kn^k+...+a_1n+a_0$

Let now $n=n_0$ such that $f(n_0)=p$, when $p$ is prime.

Let now be $t\in\mathbb{N}$, and let us look at:

$f(n_0+tp)=a_k(n_0+tp)^k+...+a_1(n_0+tp)+a_0$

$=a_kn_0^k+...+a_1n_0+a_0+pQ(t)$

$=f(n_0)+pQ(t)$

$=p+pQ(t)=p(1+Q(t))$

$Q(t)$ is polynomial with integer coefficients.

So, $p\mid{f(n_0+tp)}$, but $f(n)$ is generates primes only, therefor $f(n_0+tp)=p$ for all integer $t$.

Now, from the fact that polynomial can't have the same value more than $k$ times, we get the contradiction!

Here some interesting polynomials:

$f(n)=110,437+13,860n$ when $n=0,1,...,10$ then $f(n)$ is prime...

Also(famous one):

$f(n)=n^2+n+41$

3. Originally Posted by doug
Does there exist an f(x) minimum first-degree polynomial with integer coefficients, such that for any x integer number, f(x) is prime?

Any help would be appreciated!
If such a function existed, it would always generate prime numbers. Do some research, does that result seem reasonable?

4. Originally Posted by Also sprach Zarathustra
No!
Proof by reductio ad impossibile.
Suppose that there is exist such polynomial $f(n)$.

$f(n)=a_kn^k+...+a_1n+a_0$

Let now $n=n_0$ such that $f(n_0)=p$, when $p$ is prime.

Let now be $t\in\mathbb{N}$, and let us look at:

$f(n_0+tp)=a_k(n_0+tp)^k+...+a_1(n_0+tp)+a_0$

$=a_kn_0^k+...+a_1n_0+a_0+pQ(t)$

$=f(n_0)+pQ(t)$

$=p+pQ(t)=p(1+Q(t))$

$Q(t)$ is polynomial with integer coefficients.

So, $p\mid{f(n_0+tp)}$, but $f(n)$ is generates primes only, therefor $f(n_0+tp)=p$ for all integer $t$.

Now, from the fact that polynomial can't have the same value more than $k$ times, we get the contradiction!

Here some interesting polynomials:

$f(n)=110,437+13,860n$ when $n=0,1,...,10$ then $f(n)$ is prime...

Also(famous one):

$f(n)=n^2+n+41$
Thank you so much. Your answer is more than fantastic!
Thanks again!

5. Originally Posted by doug
Thank you so much. Your answer is more than fantastic!
Thanks again!
You are welcome!

6. Originally Posted by doug
Thank you so much. Your answer is more than fantastic!
Thanks again!
Was this a jab at mr fantastic??

7. To OP:

don't say "yes"!

8. Originally Posted by HallsofIvy
Was this a jab at mr fantastic??
No, actually it wasn't. It wasn't conscious. I just really appreciated that Also sprach Zarathustra was so kind and wrote a very clear prove.
But it might be a jab... subconsciously
I really hope that mr fantastic won't get sore.

9. Originally Posted by mr fantastic
If such a function existed, it would always generate prime numbers. Do some research, does that result seem reasonable?
There are many such functions. For example, Riemann gave an explicit formula for the number of primes less than $x$. A prime-yielding formula can be easily constructed from this.

There is also a positive constant $A$, known as Mill's constant, such that $\lfloor A^{3^n}\rfloor$ is prime for every $n$. It's about $1.306...$ if the Riemann hypothesis is correct. It yields the sequence of primes $2, 11, 1361, 2521008887, ...$.

Also, the simple recurrence relation $a_1=7, a_{n+1}=a_n+\mbox{gcd}(a_n,n)$ generates only primes.

There is no reason why any given kind of "formula for primes" could not exist. It is a popular belief that there is no such thing; I've even heard non-mathematicians claim it, as if it were some kind of established result. I don't believe the OP was asking a silly question at all, because there do exist many such formulae.

Here's another proof that no non-constant polynomial with integer coefficients yields only primes. Let $c=f(0)$ be the constant term of this polynomial. It's quite easy to see that $f(mc)$ is divisible by $c$ for every integer $m$.

10. Originally Posted by Bruno J.
Here's another proof that no non-constant polynomial with integer coefficients yields only primes. Let $c=f(0)$ be the constant term of this polynomial. It's quite easy to see that $f(mc)$ is divisible by $c$ for every integer $m$.
To Bruno J.,
I think it's a hasty assersion. Indeed $c$ divides $f(mc)$ for every integer $m$. But this only shows that a non-constant polynomial that yields only primes must have $c=1$.

11. Originally Posted by melese
To Bruno J.,
I think it's a hasty assersion. Indeed $c$ divides $f(mc)$ for every integer $m$. But this only show that a polynomial that yields only primes must have $c=1$.
But $f(0)=c$ is assumed to be prime!

12. Originally Posted by Bruno J.
But $f(0)=c$ is assumed to be prime!
But this is a special case that rules out only non-constant polynomials for which $f(0)=c$ is prime. The main result that Also sprach Zarathustra proved holds for any non-constant polynomial, whether $c$ is or isn't prime.

13. Originally Posted by melese
But this is a special case that rules out only non-constant polynomials for which $f(0)=c$ is prime. The main result that Also sprach Zarathustra proved holds for any non-constant polynomial, whether $c$ is or isn't prime.
Granted!
What I wrote still solves the original question though.