No polynomial takes only prime values
Statement
Let be a non-constant polynomial with integer coefficients. Prove that there are infinitely many integers for which is not a prime number.
Hint
Take with and . For which is divisible by ? Why can not equal for most ?
Show solutionHide solution
Solution
A value of absolute value at least . A non-constant polynomial is unbounded, so there is an integer with . Put .
Divisibility. For integer polynomials, . With , we get , so for every integer .
Large values. A non-constant polynomial takes each value at most times, so for all but finitely many , . Taking also large enough that , we get a multiple of whose absolute value is strictly larger than .
Conclusion. Such a number has the divisor with , so it is composite. This happens for infinitely many , giving infinitely many integers .
Remark. Famous examples such as are prime for many consecutive (here ), but must fail eventually (at , ).
Lesson. The congruence lets you make a polynomial value divisible by a number you control.