# Proving Polynomials Take On Composite Values

• May 14th 2010, 03:39 AM
1337h4x
Proving Polynomials Take On Composite Values
Hello all,

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!
• May 14th 2010, 04:56 AM
roninpro
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.
• May 14th 2010, 05:14 AM
1337h4x
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)?
• May 14th 2010, 05:31 AM
roninpro
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?
• May 14th 2010, 05:55 AM
1337h4x
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?
• May 14th 2010, 05:57 AM
roninpro
You need to show only that there exists an integer. Just pick \$\displaystyle d = 2\$, and then \$\displaystyle f(d)=f(2)=5\$.
• May 14th 2010, 06:11 AM
1337h4x
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?
• May 14th 2010, 06:18 AM
roninpro
It just means an infinite set. It definitely isn't true if you try to do it for all integers.
• May 14th 2010, 06:47 AM
1337h4x
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 ?
• May 14th 2010, 10:12 AM
Bruno J.
Quote:

Originally Posted by 1337h4x
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\$.
• May 14th 2010, 10:16 AM
1337h4x
Quote:

Originally Posted by Bruno J.
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\$.

Yes, but I'm talking about f(Dj+d). For example, how would one think to do this, especially if you do things like (3*2+4) is not divisible by 3.

Once again, my question remains:

Why do 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 ?