Proving Polynomials Take On Composite Values

Printable View

May 14th 2010, 03:39 AM
1337h4x

Proving Polynomials Take On Composite Values

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!
May 14th 2010, 04:56 AM
roninpro

We can just follow the hint. You should be able to show that $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 $D=f(d)$ . We will shift and stretch the polynomial by considering $f(Dj+d)=a(Dj+d)^2+b(Dj+d)+c$ . What if we expand this? We have $f(Dj+d)=aDj^2+2adDj+bDj+(ad^2+bd+c)$ . This is exactly $aDj^2+2adDj+bDj+f(d)=aDj^2+2adDj+bDj+D$ . We can see that $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 $a=1, b=1, c=0$ , then almost every output of your polynomial is automatically composite. Write $f(x)=x^2+x=x(x+1)$ . We have already (nontrivially) factored the output, for $|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 $d = 2$ , and then $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 $f(c), f(2c), f(3c),\dots$ . Each of those is divisible by $c$ .
May 14th 2010, 10:16 AM
1337h4x

Quote:

Originally Posted by Bruno J.

It's not even so complicated... Just look at $f(c), f(2c), f(3c),\dots$ . Each of those is divisible by $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 ?