Tuesday, December 12, 2006

Complexity. Topic: Complex Numbers/Polynomials. Level: AIME/Olympiad.

Problem: Let $f(x) = x^{2004}+2x^{2003}+\cdots+2004x+2005$. If $z = \cos{\frac{\pi}{1003}}+i \sin{\frac{\pi}{1003}}$ and

$N = f(z)f(z^2) \cdots f(z^{2005})$,

find the remainder when $N$ is divided $1000$. [Reworded]

Solution: Well $f$ is pretty ugly looking at the moment, let's fix that. We can write it as the sum of the following series:

$1+x+x^2+\cdots+x^{2004} = \frac{x^{2005}-1}{x-1}$

$1+x+x^2+\cdots+x^{2003} = \frac{x^{2004}-1}{x-1}$

$\cdots$

$1+x = \frac{x^2-1}{x-1}$

$1 = \frac{x-1}{x-1}$,

since all of them are geometric series with common ratio $x$. Summing these up, we have

$f(x) = \frac{x^{2005}+x^{2004}+\cdots+x+1-2006}{x-1}$.

The top is again a geometric series with common ratio $x$ (without that $2006$ part) so we can write it ias

$f(x) = \frac{\frac{x^{2006}-1}{x-1}-2006}{x-1}$.

But wait, if $x = z^k$ then $x^{2006} = (z^k)^{2006} = (z^{2006})^k = 1$, so in fact we have

$f(z^k) = \frac{2006}{1-z^k}$.

Then $N = \frac{2006^{2005}}{(1-z)(1-z^2) \cdots (1-z^{2005})$ so it remains the evaluate the denominator of that. Considering

$g(x) = (x-z)(x-z^2) \cdots (x-z^{2005})$

we are like whoa, $g$ has the $2006$th roots of unity for its roots except $x = 1$ and it has leading coefficient $1$ so it must be

$g(x) = x^{2005}+x^{2004}+\cdots+1 \Rightarrow g(1) = (1-z)(1-z^2) \cdots (1-z^{2005}) = 2006$.

Hence

$N = \frac{2006^{2005}}{g(1)} = 2006^{2004}$.

By Euler's Totient Theorem, $N \equiv 6^4 \equiv 296 \pmod{1000}$. QED.

--------------------

Comment: It didn't take too much "insight" to reduce $f$ to the nicer expression, more like just tedious evaluation of geometric series galore. Seeing the product in the denominator should have been pretty familiar (though I admit I forgot what it came out to at first) and a standard argument allowed you to evaluate it. Possibly the hardest part was Euler's Totient Theorem, which is invaluable to carry around for the AIME. Also knowing that $\phi(1000) = 400$.

--------------------

Practice Problem: Do there exist polynomials $P(x)$ and $Q(x)$ such that

$(x^8-1)P(x)+(x^5-1)Q(x) = x-1$?

If so, find them.

1 comment:

1. gcd(x^8-1, x^5-1) = x-1 by a well-known lemma so by Bezout's theorem (on polynomials!) a solution exists. We can find it by applying the Extended Euclidean Algorithm (on polynomials!).