find the remainder when p is divided by q

Let $x=2008$ , then

$p(x)=2008^{2007}-2008=x^{2007}-x$

$q(x)=2008^2+2009=2008^2+2008+1=x^2+x+1=(x-\omega)(x-\omega^2)$

Where $\omega$ is the third root of unity $e^{i\frac{2\pi}{3}}$

To find the remainder

$p(x)=(x-\omega)(x-\omega^2)h(x)+ax+b$

Where $h(x)$ is the quotient and $ax+b$ is the remainder. Now, using the facts that $2007$ is a multiple of $3$ and that $\omega$ is a third root of unity

$p(\omega)=\omega^{2007}-\omega=1-\omega$

$p(\omega^2)=(\omega^2)^{2007}-\omega^2=1-\omega^2=\omega+2$

Hence

$p(\omega)=(\omega-\omega)(\omega-\omega^2)h(\omega)+a\omega+b=a\omega+b$

$p(\omega^2)=(\omega^2-\omega)(\omega^2-\omega^2)h(\omega^2)+a\omega^2+b=-(\omega+1)a+b$

$\Longrightarrow\begin{cases} 1-\omega=a\omega+b\\ \omega+2=-(\omega+1)a+b \end{cases}$

$\Longrightarrow a=-1,b=1$

The remainder is $-x+1$ , substituting back $x=2008$

$-x+1=-2007\equiv \boxed{4032066}\mod (2008^2+2009)$

---

Note:

$\omega^{2007}=\left(e^{i\frac{2\pi}{3}}\right)^{2007}=\left[\left(e^{i\frac{2\pi}{3}}\right) ^3\right]^{669}=1^{669}=1$

$\omega$ is a root of $x^2+x+1$ , hence

$\omega^2+\omega+1=0\Longrightarrow \omega^2=-(\omega+1)$