Proving Polynomials Take On Composite Values

Apr 2009
96
0
Hello all,

I was reading on the internet about this but I cannot seem to find a proof.

Let f(x)=ax^2 + bx + c be a non-constant polynomial, and assume that a, b, and c are integers.
Prove that there are infinitely many integers n such that f(n) is compsite.

As a hint to the prove, the author noted "Show that there is an integer d such that f(d) has absolute value greater than 1. Let D=f(d), and then show that D divides f(Dj+d) for every integer j."


Any help would be appreciated!
 
Nov 2009
485
184
We can just follow the hint. You should be able to show that \(\displaystyle f\) attains a value whose absolute value is more than 1. (It's a little bit of a trivial matter.) Now, let that value be \(\displaystyle D=f(d)\). We will shift and stretch the polynomial by considering \(\displaystyle f(Dj+d)=a(Dj+d)^2+b(Dj+d)+c\). What if we expand this? We have \(\displaystyle f(Dj+d)=aDj^2+2adDj+bDj+(ad^2+bd+c)\). This is exactly \(\displaystyle aDj^2+2adDj+bDj+f(d)=aDj^2+2adDj+bDj+D\). We can see that \(\displaystyle D\) divides this.
 
Apr 2009
96
0
roninpro, I would specifically like to examine the case of x=0, and x=-1 where a,b=1, c=0.
f(0)=1(0^2)+1(0) = 0, so |f(0)|!=1.
f(-1)=(1)(-1^2)+1(-1) = 0, so |f(-1) |!=1.
It is only for values |k|>1 does |f(k)|=y where y>=1.

So how do we make these series of statements knowing this (when there are exceptions of 0 and -1 under these conditions)?
 
Nov 2009
485
184
Actually, every number (except 0) divides 0, so the cases you mentioned are not exceptions.

If you put \(\displaystyle a=1, b=1, c=0\), then almost every output of your polynomial is automatically composite. Write \(\displaystyle f(x)=x^2+x=x(x+1)\). We have already (nontrivially) factored the output, for \(\displaystyle |x|\geq 2\).

Do you want to pick other coefficients?
 
Apr 2009
96
0
I guess what I don't understand is that f(0) and f(-1) yield zero, but the statement says:

Show that there is an integer d such that f(d) has absolute value greater than 1.

How is this true if when d=0,-1 that statement is false?
 
Nov 2009
485
184
You need to show only that there exists an integer. Just pick \(\displaystyle d = 2\), and then \(\displaystyle f(d)=f(2)=5\).
 
Apr 2009
96
0
I understand that there exists AN integer k, but |k|>1. This isn't true for all integers. The statement says:
Prove that there are infinitely many integers n such that f(n) is compsite.

So when it says infinitely many, does that imply ALL integers or just an infinite set that has those exclusions?
 
Nov 2009
485
184
It just means an infinite set. It definitely isn't true if you try to do it for all integers.
 
Apr 2009
96
0
Okay, so can you explain to me why we say D=f(d) and then we do f(Dj+d) ? How would one know to do such a thing? I mean, what are we getting out of that and how is that the way we would go about stating that there are infinitely many integers n such that f(n) is compsite ?
 

Bruno J.

MHF Hall of Honor
Jun 2009
1,266
498
Canada
Okay, so can you explain to me why we say D=f(d) and then we do f(Dj+d) ? How would one know to do such a thing? I mean, what are we getting out of that and how is that the way we would go about stating that there are infinitely many integers n such that f(n) is compsite ?
It's not even so complicated... Just look at \(\displaystyle f(c), f(2c), f(3c),\dots\). Each of those is divisible by \(\displaystyle c\).
 
  • Like
Reactions: Isomorphism