x^n を割った余り｜1 の 3 乗根と二項定理

$x^{100}$ を $x^2-1$ で割った余りを求めます。割り算を $100$ 回まわす道はありません。余りを $ax+b$ と置いて、因数を $0$ にする値を代入します。

$$x^{100}=(x-1)(x+1)Q(x)+ax+b$$

$x=1$ で $1=a+b$、$x=-1$ で $1=-a+b$。解いて $a=0$, $b=1$。余りは $1$ です。

指数が大きくても、代入する値が $\pm 1$ なら計算は一瞬。ここまでは $2$ 次式で割る手順そのままです。

代入できない因数のとき

$x^{100}$ を $x^2+x+1$ で割る場合は事情が違います。$x^2+x+1=0$ の解は実数ではないので、代入する実数がありません。

そこで別の道具を使います。$1$ の $3$ 乗根 $\omega$ です。$\omega$ は $x^2+x+1=0$ の解で、次の $2$ つを満たします。

$${\omega }^3=1,{\omega }^2+\omega +1=0$$

$3$ 乗すると $1$ に戻る。この周期性が効きます。

$\omega$ を掛けるたびに $\frac{1}{3}$ 周ずつ進み、$3$ 回で出発点に戻ります。指数を $3$ で割った余りだけを見ればよい、ということです。

余りを求める

$x^{100}=(x^2+x+1)Q(x)+ax+b$ に $x=\omega$ を代入します。${\omega }^2+\omega +1=0$ なので第 $1$ 項が消える。

$${\omega }^{100}=a\omega +b$$

左辺を整理します。$100=3\cdot 33+1$ なので ${\omega }^{100}=({\omega }^3{)}^{33}\cdot \omega =\omega$。したがって

$$\omega =a\omega +b$$

$\omega$ は実数ではないので、$a=1$, $b=0$。余りは $x$ です。

$\omega$ が実数でないことから係数を比較する部分は、$\omega$ が $1$ 次式で書けないことを使っています。$a$, $b$ が実数なら、$(a-1)\omega +b=0$ から $a-1=0$ と $b=0$ が出る。

二項定理で押す道

$\omega$ を使わずに済ませる方法もあります。指数を割る式に合わせて書き直す手です。

$x^{100}$ を $(x-1{)}^2$ で割った余りを求めます。$x=(x-1)+1$ と見て、二項定理で展開する。

$$x^{100}=\{(x-1)+1{\}}^{100}=\sum _{k=0}^{100}{}_{100}{\mathrm{C}}_k(x-1{)}^k$$

$(x-1{)}^2$ 以上の項はすべて割り切れるので、余りに残るのは $k=0$ と $k=1$ の項だけ。

$${}_{100}{\mathrm{C}}_0+{}_{100}{\mathrm{C}}_1(x-1)=1+100(x-1)=100x-99$$

代入では $1$ 本しか式が立たない重解の場合を、この方法なら正面から処理できます。

展開した $101$ 項のうち、生き残るのは左端の $2$ つだけ。残りはすべて $(x-1{)}^2$ を因数に持つので、割り算で消えます。

どちらを選ぶか

割る式の形で決まります。

$x^2+1$ で割るときは $i$ を代入します。$i^2=-1$ から $i^4=1$ で、こちらは $4$ の周期。$\omega$ の $3$ 周期と同じ発想です。

指数が大きい問題は、必ずどこかに周期か打ち消しが仕込まれています。それを探すのが最初の一手になります。