Problem: Let $ f(x) $ be a polynomial with integer coefficients. Show that $ f(a) $ divides $ f(a+f(a)) $.
Solution: Note that $ a|b $ means $ a $ divides $ b $. Let's prove a more general result, that $ (x-y)|(f(x)-f(y)) $. Write $ \displaystyle f(x) = \sum c_nx^n $. We want to show that
$ \displaystyle (x-y)|\left(\sum c_n(x^n-y^n) \right) $.
But since $ x^n-y^n = (x-y)(x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1}) $, it's clear that $ x-y $ divides each $ c_n(x^n-y^n) $ and thus their sum. Applying this result to $ x = a+f(a) $ and $ y = a $, we get
$ \displaystyle f(a)|(f(a+f(a))-f(a)) $,
which implies that
$ \displaystyle f(a)|f(a+f(a)) $,
as desired. QED.
--------------------
Comment: The general result is a very useful fact about polynomials with integer coefficients that shows up often; problems can be written based on many variations of it. Writing out the terms of the polynomial is also a good strategy whenever you're stuck.
--------------------
Practice Problem: Let $ f(x) $ be a polynomial with integer coefficients. If $ a, b, c, d $ are distinct integers such that $ f(a) = f(b) = f(c) = f(d) =5 $, show that there cannot exist an integer $ e $ such that $ f(e) = 8 $.
I"ve seen that problem a lot.
ReplyDeletef(x) - 5 has four distinct integer roots, but
3 = (x-a)(x-b)(x-c)(x-d)
Has no integer solution for distinct a, b, c, d. QED.
is the practice problem usually easier than the example above??
ReplyDeleteanywayz,
so f(x) is a 4th degree polynomial...? can it be written like:
f(x) = (x-a)(x-b)(x-c)(x-d) or should it be like: f(x)=ax^4+bx^3+cx^2+dx? hmm.. this probably has nothing to do with solving it. .. but i'm just trying to understand the problem. >
Sometimes practice is harder; sometimes easier. It's not necessarily 4th degree, but QC made a super-simplified skipping step solution :P. Basically
ReplyDeletef(x)-5 = Q(x)(x-a)(x-b)(x-c)(x-d)
because a, b, c, d are roots (plug into that equation to see). But if f(e) = 8, then
f(e)-5 = 3 = Q(e)(e-a)(e-b)(e-c)(e-d).
However, since |(e-a)(e-b)(e-c)(e-d)| >= |1*(-1)*2*(-2)| = 4, there are no solutions.
Well, you left out the case f(e) - 5 = 0. ;)
ReplyDeleteIt was implicitly covered -__-. Lol.
ReplyDeleteIn any case, the lemma in the original problem is obvious if you rewrite x and y as polynomials of a third parameter t and consider the field Z[t]_{ x(t) - y(t) }.
ReplyDelete:P
um.. okay. thanks ^^
ReplyDeleteI worded that poorly. Just consider Z[x, y]_{x - y}, which is actually guaranteed to be a field, haha.
ReplyDeleteIsn't there a simpler solution? We just showed that e-d,e-c,e-b, and e-a all divide f(e)-5=3, but this is impossible in integers? Doesn't this also generalize to many more numbers than just 8 for f(e)?
ReplyDeleteThat's the same idea, just put in a different way, but yeah that would work. It generalizes to any 5+p where p is prime I think, because primes cannot be written as the product of four distinct integers, but composites can.
ReplyDelete