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.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestLet 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.

Log in to reply

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.

Log in to reply

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 (c

n)(x^n) + (c(n-1))(x^(n-1)) ... + c_0WLOG we can assume c_n is positive; otherwise, multiply the polynomial by -1.

Let abs(c

0) + abs(c1) + ..+ abs(c_(n-1)) = CObserve that abs ((c

(n-1))(x^(n-1)) + (c(n-2))(x^(n-2))... + c_0) <= C (x^(n-1)) for sufficiently large xAs 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.

Log in to reply

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

Please express your thoughts on the above question, guys.

Log in to reply

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.

Log in to reply

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 \) ?

Log in to reply

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.

Log in to reply

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.

Log in to reply

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.

Log in to reply

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.

Log in to reply

Log in to reply

Log in to reply

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

Log in to reply