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.
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!).
ReplyDelete