Follow up to problem E9 - Composite values of integer polynomials

I’ve been doing some more thinking about Problem E9, which asks the reader to prove that the range of a quadratic polynomial evaluated on the integers must include a composite number. In addition to the algebraic proof I linked to the original problem, my brother provided a proof based on congruences. I think both are interesting.

Each proof applies to all non-trivial polynomials, not just quadratics, and each actually shows (or can be extended to show) that the range of the polynomial must include an infinite number of composite numbers.

One question to which I do not know the answer is whether the range of a polynomial must contain an infinite number of prime numbers. Of course, the answer is “no” if the polynomial factors over the integers. If the polynomial is prime, however, I suspect the answer is “yes”.

For linear polynomials, the prime or composite nature of the ranges have been well studied. In 1837, Dirichlet proved that every sequence (an + b) contains an infinite number of prime numbers, iff (a, b) = 1, and moreover the fraction of all primes ≤ x that are in such a sequence approaches 1/φ(a) as x approaches infinity, where φ(a) is the number of natural numbers less than a that are relatively prime to a. As a corollary, this also shows that there are an infinite number of composite numbers in the range.

Dirichlet’s Theorem is famous for being the first that used complex analysis to solve a major problem in number theory. Recently (2004), Green and Tao (in an important and difficult paper) proved that there exist arithmetic sequences of arbitrary length that are all prime. The proof is non-constructive.