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.