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.

I recently encountered this following proposition:

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

2 Answers 2

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
    
Thanks for the answer! Only one thing to point out: when the leading coefficient is negative, we know that for $x$ sufficiently large, $P(x)<0$, which cannot be a prime. :) –  Bill Liu Oct 26 at 12:32
    
You are elcome. Sometimes, particularly if one is algebraic number theory minded, something like $-13$ is considered prime. That's why at the beginning I said ithout loss of generality we can take the lead coefficient positive. –  André Nicolas Oct 26 at 15:15

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

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.