x²−x+1 で割った余り(周期6のべき)

方針

解答

⓪ 発想 — どう考え始めるか。 2次式で割った余りは $px+q$ とおき、割る式の解を代入して係数を決めるのが定石だ。

割る式 $x^2-x+1=0$ の解 $\zeta$ は虚数だが、$\zeta$ のべきに周期があれば ${\zeta }^{100}$ は楽に計算できる。ここで因数分解 $x^3+1=(x+1)(x^2-x+1)$ に気づくのが急所。$\zeta$ は $x^3+1=0$ の解でもあるから ${\zeta }^3=-1$、つまり ${\zeta }^6=1$ で周期6の循環が起きる。

① 設定。 $x^{100}=(x^2-x+1)Q(x)+px+q$($p,q$ は実数)とおく。$x^2-x+1=0$ の虚数解の1つを $\zeta$ とすると

$${\zeta }^{100}=p\zeta +q$$

② ${\zeta }^{100}$ を計算する。 ${\zeta }^2-\zeta +1=0$ の両辺に $\zeta +1$ を掛けると ${\zeta }^3+1=0$、すなわち ${\zeta }^3=-1$。$100=3\times 33+1$ だから

$${\zeta }^{100}=({\zeta }^3{)}^{33}\cdot \zeta =(-1{)}^{33}\zeta =-\zeta$$

③ 係数を比べる。 $p\zeta +q=-\zeta$ より $(p+1)\zeta =-q$。もし $p+1\ne 0$ なら $\zeta =\frac{-q}{p+1}$ は実数となり、$\zeta$ が虚数であることに反する。よって $p+1=0$ かつ $q=0$、つまり $p=-1,q=0$。

$$\text{余り}=-x$$

まとめ: 「割る式の解を代入」+「解のべきの周期」の合わせ技。$x^2+x+1$ なら解は $x^3=1$(周期3)、$x^2-x+1$ なら $x^3=-1$(周期6)。この対をセットで覚えておくと、巨大なべきの剰余が瞬時に読める。

発展 — 一歩先へ。 周期6の表を一度作っておくと万能になる。$x^n$ の余りは $n$ を6で割った余りだけで決まり、順に $1,x,x-1,-1,-x,-x+1$。$100\equiv 4(\mathrm{mod}6)$ で表から $-x$。どんな巨大な $n$ でも即答できる。

別解

虚数を使わない(多項式の合同ルート)。 数の合同式とまったく同じ作法が、多項式でも通る。

割り算 $x^3+1=(x^2-x+1)(x+1)$ を移項すると

$$x^3=(x^2-x+1)(x+1)-1$$

つまり、$x^2-x+1$ で割った余りの世界では $x^3\equiv -1$ と「みなして」よい($x^3$ を $-1$ に置き換えても、余りは変わらない)。すると

$$x^{100}=(x^3{)}^{33}\cdot x\equiv (-1{)}^{33}x=-x$$

余りは1次以下の $-x$ そのものだから、これが答えだ。

虚数解 $\zeta$ に頼らず、「割る式の倍数を自由に足し引きしてよい」という割り算の原理だけで進む。数の合同(たとえば mod 7 で $10\equiv 3$)と同じ感覚を多項式に持ち込む、と覚えると視界が広がる。