Difference between revisions of "2008 iTest Problems/Problem 80"

Revision as of 17:49, 16 September 2008

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}$ .

Page

Toolbox

Search

Difference between revisions of "2008 iTest Problems/Problem 80"

Revision as of 17:49, 16 September 2008

Problem

Solution

See also