# Prime Polynomial

This question has been troubling me from a couple of days: Does there exist a non-constant polynomial with integer coefficients that takes only prime values? Why, Why not?

I feel that there exists no such polynomial, but I am unable to prove it. Somebody please help me out.

5 years, 6 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

Let the highest coefficient of the polynomial be Ax^N. Observe that the polynomial must always take on prime values (I assume for all positive integers x, p(x) is prime) and must thus be positive. Thus A is positive. Also let the sum of the (positive) coefficients in the polynomial be B.

From Prime number theorem, the number of primes from 1 to M is less than 2 log M

The number of primes in (1,2,...M) is less than 2 log M. However, the number of values from 1 to M that are mapped to by the polynomial is at least (M/B)^(1/N), for large enough M. Observe that this value grows much faster than log M, thus for sufficiently large M at least one value mapped to by the polynomial will not be prime.

In other words: density of primes < density of numbers mapped to by polynomial.

- 5 years, 6 months ago

Note that $$-2$$ is a prime, so you need to be careful. If such a polynomial existed, you could multiply it by $$-1$$, and so $$A$$ could be negative.

Density is a good way of looking at it. You have not provided any justification for your bound, how you obtained it. A slightly simpler argument is to say that $$\{ f(n) \} _{i=1} ^M$$ has at least $$\frac{M}{N}$$ distinct values by the Fundamental Theorem of Algebra.

Staff - 5 years, 6 months ago

If we allow negative numbers as primes (e.g. -2), here is a revised proof:

We only need to show p(x) cannot take prime values for all positive integers x. Let p(x) take the form of (cn)(x^n) + (c(n-1))(x^(n-1)) ... + c_0

WLOG we can assume c_n is positive; otherwise, multiply the polynomial by -1.

Let abs(c0) + abs(c1) + ..+ abs(c_(n-1)) = C

Observe that abs ((c(n-1))(x^(n-1)) + (c(n-2))(x^(n-2))... + c_0) <= C (x^(n-1)) for sufficiently large x

As long as x is sufficiently large, (c_n)(x^n) > C (x^(n-1). It is then clear that p(x) only takes positive values.

Consider p(D+1), p(D+2) .... p(ED), which must all be prime, for sufficiently large integers D, E. Let the sum of all c_i be F.

It is clear that p takes a maximum value of F(ED^n). Thus, all values that p takes from D+1 to ED are contained in the region (1,F(ED^n)).

Number of primes in this region < 2log(F(ED^n)) = 2log F + 2n log(E) + 2n log (D)

Number of values p takes in this region >= (E-1)D

As F and n are constant, it is then clear due to the growth rates of the functions, that as long as E and D are sufficiently large, the number of values p takes in the region is much larger than the number of primes, completing the proof.

- 5 years, 6 months ago

Can such an infinite polynomial exist? How to approach such a problem? What are the properties of an infinite polynomial?

- 5 years, 6 months ago

Let the constant term of the polynomial be a. If a=0 then f(0) is not prime. Suppose $$a\neq0$$. Then f(a)=a (a must be a prime subject to given conditions) since f(a) is divisible by a . Also f(ka)=a $$\forall k \in I$$. Consider the polynomial f(x)-a. It is a polynomial of finite degree having infinitely many roots. This not possible unless f(x) is identically equal to 0. But according to our assumption a is not 0. Hence, proved.

- 5 years, 6 months ago

You need to be careful with your proofs. Make sure you write down everything that's in your head, as the rest of us are not mind-readers.

Your proof is currently incomplete: 1. I believe that you are missing the sentence "If $$a$$ is composite, then $$f(0)$$ is not prime".
2 You also need to justify why $$f(a) = a$$. Why can't we have $$f(a) = -a$$ ?

Staff - 5 years, 6 months ago

I thought that primes should be considered positive, unless otherwise stated. http://en.wikipedia.org/wiki/Prime_number and http://mathworld.wolfram.com/PrimeNumber.html define primes over positive integers.

- 5 years, 6 months ago

I found a much simpler proof. Here it goes:  Consider $$p(x)=a_n x^n+a_{n-1}x^{n-1}...a_1 x^1 + a_0 = m.$$ Now consider $$p(x+m)$$. By expanding, we get that $$m$$ divides $$p(x+m).$$ So, such a polynomial doesn't exist.

- 5 years, 6 months ago

How does only showing that m|p(x+m) prove that such a polynomial doesn't exist? m can be a prime and p(x+m) can be m. In my opinion, a little more explanation is required.

- 5 years, 6 months ago

I think this proof is alright. We claim that such a prime polynomial exists. But then we show that for $$p(x+m)$$ , it can be divided by $$m$$. Then no matter what $$m$$ is, a prime or composite. And $$p(x+m)$$ cannot be $$m$$. I guess the proof is complete.

- 5 years, 6 months ago

But you didn't prove why p(x+m) can't be m.

- 5 years, 6 months ago

Can someone help me out here?

- 5 years, 6 months ago

Hint: Set $$m = p(0)$$, which is prime by assumption. What does this tell us about the possible values of $$p(n)$$ where $$n$$ is an integer?

Hint: Any finite degree polynomial which takes on a value infinitely often is the constant polynomial.

Staff - 5 years, 6 months ago