Let P(x) be a nonconstant polynomial, where all the coefficients are nonnegative integers. Prove that there exist infinitely many positive integers n such that P(n) is composite.
Remember that if a and b are distinct integers, then P(a) - P(b) is divisible by a - b.
a few seconds with google led me to
https://math.stackexchange.com/questions/304330/proof-of-lack-of-pure-prime-producing-polynomials
that should get you started.
Why did the polynomial go to the comedy show? Because it wanted to prove that it could generate infinitely many laughs!
To prove that there exist infinitely many positive integers n such that P(n) is composite, let's assume the contrary, that is, a finite number of positive integers exist such that P(n) is composite.
Now, let's consider the polynomial P(x) - P(1). Since the coefficients of P(x) are non-negative integers, P(1) is a non-negative integer. Therefore, P(x) - P(1) is a polynomial with non-negative integer coefficients.
Now, let's denote Q(x) = P(x) - P(1). We know that Q(x) is a non-constant polynomial, and all its coefficients are non-negative integers.
Since a and b are distinct integers, according to the given fact, we can conclude that Q(a) - Q(b) is divisible by a - b.
If we substitute x = n, where n is a positive integer, into the equation Q(x) - Q(1), we get Q(n) - Q(1).
Since Q(n) - Q(1) is divisible by n - 1, we can observe that for any composite number C, if n - 1 is a divisor of C, then Q(n) - Q(1) will also be divisible by C.
However, since we initially assumed that P(n) is not composite for infinitely many positive integers n, the set of positive integers for which n - 1 is a divisor of Q(n) - Q(1) must be finite.
Since there are infinitely many composite numbers, there must exist a composite number, C, that is not in this finite set.
Now, if we choose n = C + 1, we observe that n - 1 = C, which is a divisor of C. Therefore, Q(n) - Q(1) must also be divisible by C, which implies that P(n) - P(1) is divisible by C.
However, P(n) - P(1) simplifies to P(C + 1) - P(1), which means that P(C + 1) is divisible by C. Since C is a composite number, we have proven that for infinitely many positive integers n = C + 1, P(n) is composite.
Therefore, our initial assumption was incorrect, and we have proven that there exist infinitely many positive integers n such that P(n) is composite. Isn't polynomial math hilarious?
To prove that there exist infinitely many positive integers n such that P(n) is composite, we can use a proof by contradiction.
Assume that there are only finitely many positive integers n such that P(n) is composite. Let's call this finite set of integers S = {n1, n2, n3, ..., nk}.
Now, let's consider the polynomial P(x) - P(n1). Since P(x) is a nonconstant polynomial, it has infinitely many integer solutions. In other words, there exist infinitely many positive integers x such that P(x) - P(n1) = 0.
Now, let's examine the difference P(x) - P(n1). According to the given information, since a and b are distinct integers, P(a) - P(b) is divisible by a - b. Therefore, for any positive integer x, we have P(x) - P(n1) is divisible by x - n1.
Let's consider a positive integer x that is not in S. Since x is not equal to any of the elements in S, we can choose a particular element nj from S such that nj is not equal to x. Therefore, x - nj is non-zero, and thus, P(x) - P(nj) is divisible by x - nj.
Now, let's take x - nj as a factor, where nj is some element in S. Since there are only finitely many elements in S, we have x - nj as a factor for infinitely many positive integers x (since there are infinitely many positive integers).
Let's define Q(x) as the polynomial obtained when we divide P(x) - P(nj) by x - nj. Q(x) will also have nonnegative integer coefficients since it is obtained by dividing a polynomial with nonnegative integer coefficients by an integer.
Now, let's consider the value of Q(nj). We have Q(nj) = P(nj) - P(nj) = 0.
To summarize, for any positive integer x that is not in S, we have Q(x) = 0 when x - nj is a factor, where nj is some element in S. But this means that Q(x) has infinitely many positive integer roots, which contradicts the fact that Q(x) is a nonconstant polynomial.
Therefore, our assumption that there are only finitely many positive integers n such that P(n) is composite is false. Hence, there must exist infinitely many positive integers n such that P(n) is composite.