Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Now I have heard this (correct me if I am wrong) that for every polynomial, there is some positive integer for which it is composite. What is the most elementary proof of this.

share|improve this question
    
Note, there is a multiple variable polynomial whose positive values are all the primes: en.wikipedia.org/wiki/Formula_for_primes (but it has some garbage negative values) –  user58512 Feb 14 '13 at 21:46
    
I'm almost certain this has been answered at least a couple times before, but I had no luck locating the prior posts. Anyone? –  Math Gems Feb 14 '13 at 23:07
add comment

2 Answers

up vote 2 down vote accepted

Not quite true, look at the polynomial $17$. And the usual theorem specifies that the polynomial has integer coefficients.

Let $P(x)$ be a non-constant polynomial with integer coefficients. Without loss of generality we can assume that its lead coefficient is positive.

It is not hard to show that there is a positive integer $N$ such that for all $n\ge N$, we have $P(n)\gt 1$, and such that $P(x)$ is increasing for $x\ge N$. (For large enough $x$, the derivative $P'(x)$ is positive.)

Let $P(N)=q$. Then $P(N+q)$ is divisible by $q$. But since $P(x)$ is increasing in $[N,\infty)$, we have $P(N+q)\gt q$. Thus $P(N+q)$ is divisible by $q$ and greater than $q$, so must be composite.

Remark: One can remove the "size" part of the argument. For any $b$, the polynomial equation $P(x)=b$ has at most $d$ solutions, where $d$ is the degree of $P(x)$. So for almost all integers $n$, $P(n)$ is not equal to $0$, $1$, or $-1$.

Let $N$ be a positive integer such that $P(n)$ is different from $0$, $1$, or $-1$ for all $n\ge N$. Let $P(N)=q$. Consider the numbers $P(N+kq)$, where $k$ ranges over the non-negative integers. All the $P(N+kq)$ are divisible by $q$. But since the equations $P(n)=\pm q$ have only finitely many solutions, there is a $k$ (indeed there are infinitely many $k$) such that $P(N+kq)$ is not equal to $\pm q$, but divisible by $q$. Such a $P(N+kq)$ cannot be prime.

I prefer using considerations of size.

share|improve this answer
add comment

Suppose $P$ is a polynomial, then it is periodic mod $m$: I mean $P(a) = P(a+m) \pmod m$.

Suppose it takes on different prime values like $p$ and $q$.

Then $P(x) \equiv 0 \pmod p$ for some $x$, and $P(y) \equiv 0 \pmod q$ for some $y$. By periodicity we can find a $z$ such that $pq|P(z)$ using periodicity.

share|improve this answer
add comment

Your Answer

 
discard

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.