## 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??
anywayz,
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) }.

:P

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.