OMCE011(D) - 地道に計算する

　公式解説と同様に， $$\begin{aligned} P(x) &= Q(x)(x^{3000}+x^{2999}+\cdots +x+1)+3001\\ & = R(x)(x^{7000}+x^{6999}+\cdots +x+1)+7001 \end{aligned}$$ とおく．まずは $P(x),Q(x),R(x)$ の次数を考えよう．
　$R(x)$ が $k$ 次式だとすれば，$Q(x)$ は $(k+4000)$ 次式であり，それぞれ $(k+1), (k+4001)$ の係数（定数項含む）の値が未知数となる．一方，$P(x)$ は$(k+7000)$ 次式なので，最初の式より $(k+7001)$ 個の方程式ができる．方程式が解を持つためには未知数以上の方程式の本数が必要なので，$k \geq 2998$ であれば解を求められる．
　以下， $$R(x)=a_0+a_1 x+a_2 x^2+ \cdots + a_{2997} x^{2997}+ a_{2998} x^{2998}$$ とおいて，$R(x)$ の係数たちを決定していく．
　最初の式を $(x-1)$ 倍すると， $$R(x)(x^{7001}-1)+4000(x-1)$$ は $(x^{3001}-1)$ を因数に持つ．次数を落として， $$R(x)(x^{999}-1)+4000(x-1)$$ が $(x^{3001}-1)$ で割り切れればよい．ここで $R(x)=\sum a_k x^k$ の式を用いて整理すると上の式は次のように書ける： $$\begin{aligned} &a_{2998}x^{3997}+\cdots+a_{2004}x^{3003}+a_{2003}x^{3002}+a_{2002}x^{3001}\\ &+a_{2001}x^{3000}+a_{2000}x^{2999}+(a_{1999}-a_{2998})x^{2998}+\cdots+(a_0-a_{999})x^{999}-a_{998}x^{998}-a_{997}x^{997}\\ &-a_{996}x^{996}\cdots-a_3x^3-a_2x^2-(a_1-4000)x-(a_0+4000) \end{aligned}$$ 以上の式が $(x^{3001}-1)$ で割り切れることから，以下のことがわかる：

• $a_0+4000=a_{2002}, a_1-4000=a_{2003}$
• $a_k=a_{k+2002}$　ただし $2 \leq k \leq 996$
• $a_{997}, a_{998}, a_{2000}, a_{2001}$ はいずれも $0$
• $a_k=a_{k+999}$　ただし $0 \leq k \leq 1999$

　上から条件 1, 2, 3, 4 と呼ぶことにする．
　条件 2 と条件 4 から，$2 \leq k \leq 996$ の範囲で $a_k=a_{k+4}$ である．このこととと条件 3，条件 4 を用いると $a_2, a_3, a_5$ はいずれも $0$ である．（なお，さらに条件 2，条件 4 を用いれば $a_n=0$ を満たす $n$ はたくさんある．）
　$a_{2003}=0$ より $a_1=4000$ を得，これより $$a_1=a_4=\cdots=a_{1000}=a_{1003}=\cdots=a_{1999}=a_{2002}=\cdots=a_{2998}=4000$$ である．最後に，$a_0=0$ を得る．

　求めたいものは $P(1)$ だった．$R(1)=4000 ×751=3004000$ であり， $$P(1)= 3004000\cdot 7001 +7001=\mathbf{21031011001}$$