Going through some old number theory notes, I came across a result concerning generating prime numbers that I (embarrassingly) had forgotten. It would be a great topic to present to my students–if I were still teaching…sigh. As with many of my posts, we begin with a question.
Does there exist a function whose set of values consists of only primes and all the primes? The answer is yes, but the result is computationally involved and I will postpone any further commentary on such a function until the end. However, there does not exist a polynomial which
The first result is due to Christian Goldbach, who showed that there does not exist a univariate polynomial which returns a prime for all but finitely many values. I do not know the exact publication of this result, but more than one author states that he demonstrated this result in 1752. The exposition of the proof is adapted from G. Everest and Thomas Ward, An Introduction to Number Theory.
- If has the property that is prime for all , then is constant.
- If has the propery that is prime for all , for some natural number , then is constant.
Proof. We first prove statement (2), as it implies statement (1). Let be a polynomial of degree with integer coefficients such that is prime, for all .
Suppose that is prime. Since the polynomial has at most roots, we can find an integer such that . By the binomial theorem,
is prime with . But divides both terms of the right-hand side, which contradicts the primality of .
The second result, which I believe is also due to Goldbach, is that there does not exist a polynomial in two or more variables whose set of values is only the primes. The proof of this result constructs a univariate function from , which returns infinitely many composite values.
Proposition 2. Let be a polynomial in variables with integer coefficients. Define a function by
and assume that as . Then is composite for infinitely many values of .
Proof. Fix . Since we can rewrite a factor of the form as
Enumerate the terms in ascending order by
Allowing for zero coefficients , we can rewrite as
Since the terms of are arranged in ascending order, we see that dominates all the terms of as . Suppose that is prime for all sufficiently large . Then the coefficient is necessarily positive. Since , by hypothesis, as , we see that there exists a positive integer such that
For positive integers and ,
By Fermat’s little theorem, , for . Hence,
for all positive integers and . Hence,
Substituting in this result, we conclude that
for all positive integers . This result is a contradiction as the hypothesis that as implies that there exists a such that , where is a prime.
The second result shows that multivariable integer polynomial cannot be used to efficiently generate primes either. Without further testing, we do not know if a given value of is prime or composite.
According to Hardy and Wright, it is possible to construct an integral polynomial in several variables such that the positive values assume all the primes and only the primes; however, its negative values are composite. Davis, Matijasevic, Putnam, and Robinson showed that with k=42, the degree of the poylnomial need not be more than 5. Hardy and Wright state that the minimal value of k for such a polynomial is k=10; however, the degree of in this case is 15905. The interested reader can consult Jones, Sato, Wada, and Wiens, American Math. Monthly 83 (1976), 449-65.