Friday, August 18, 2006

Effuvay. Topic: Algebra/NT/Polynomials. Level: AIME.

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 $.


  1. I"ve seen that problem a lot.

    f(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.

  2. is the practice problem usually easier than the example above??
    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. >

  3. Sometimes practice is harder; sometimes easier. It's not necessarily 4th degree, but QC made a super-simplified skipping step solution :P. Basically

    f(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.

  4. Well, you left out the case f(e) - 5 = 0. ;)

  5. It was implicitly covered -__-. Lol.

  6. In 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) }.


  7. um.. okay. thanks ^^

  8. I worded that poorly. Just consider Z[x, y]_{x - y}, which is actually guaranteed to be a field, haha.

  9. Isn'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)?

  10. That'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.