2008 iTest Problems/Problem 80

Revision as of 17:49, 16 September 2008 by Azjps (talk | contribs) (solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

Let

$p(x) = x^{2008} + x^{2007} + x^{2006} + \cdots + x + 1,$

and let $r(x)$ be the polynomial remainder when $p(x)$ is divided by $x^4+x^3+2x^2+x+1$. Find the remainder when $|r(2008)|$ is divided by $1000$.

Solution

$x^4+x^3+2x^2+x+1 = (x^2 + 1)(x^2 + x + 1)$. We apply the polynomial generalization of the Chinese Remainder Theorem.

Indeed,

$p(x) = (x^{2008} + x^{2007} + x^{2006}) + \cdots + (x^4 + x^3 + x^2) + x + 1 \equiv x+1 \pmod{x^2 + x + 1}$

since $x^{n+2} + x_{n+1} + x^{n} = x^{n-2}(x^2 + x + 1) \equiv 0 \pmod{x^2 + x + 1}$. Also,

$p(x) = (x^{2008} + x^{2006}) + (x^{2007} + x^{2005}) + \cdots + (x^4 + x^2) + (x^3 + x) + 1 \equiv 1 \pmod{x^2 + 1}$

using similar reasoning. Hence $p(x) \equiv x+1 \pmod{x^2 + x + 1}, p(x) \equiv 1 \pmod{x^2 + 1}$, and by CRT we have $p(x) \equiv -x^2 \pmod{x^4+x^3+2x^2+x+1}$.

Then $|r(2008)| \equiv 2008^2 \equiv 64 \pmod{1000}$.

See also

Invalid username
Login to AoPS