整式を2次式で割った余り

方針

解答

⓪ 発想 — どう考え始めるか。 $x^{2024}$ を割るのは無理。$x^2-x+1$ を法として、次数を下げる。$x^2\equiv x-1$。

さらに、$x^2-x+1$ が $x^3+1$ の因数であることに気づきたい。$(x^2-x+1)(x+1)=x^3+1$ だから、$x^3\equiv -1$、したがって $x^6\equiv 1$。

これで指数を $6$ で割った余りに落とせる。$2024=6\cdot 337+2$ より $x^{2024}\equiv x^2\equiv x-1$。余りは $x-1$。

① $x^3$ の関係を作る。 $(x^2-x+1)(x+1)=x^3+1$ だから、$x^2-x+1$ で割った余りを考える世界では

$$x^3\equiv -1,x^6=(x^3{)}^2\equiv 1$$

② 指数を $6$ で割った余りに帰着。 $2024=6\times 337+2$ だから

$$x^{2024}=(x^6{)}^{337}\cdot x^2\equiv 1^{337}\cdot x^2=x^2$$

③ $x^2$ をさらに下げる。 $x^2-x+1=0$ とみて $x^2\equiv x-1$。よって

$$x^{2024}\equiv x^2\equiv x-1$$

余りは $x-1$。

まとめ:高い累乗の余りは「割る式から周期を作る」。$x^2-x+1$ は $(x+1)$ を掛けると $x^3+1$ になり、$x^3\equiv -1$、$x^6\equiv 1$ の周期 $6$。指数 $2024$ を $6$ で割った余り $2$ に落とし、最後に $x^2\equiv x-1$ で $1$ 次まで下げる。

発展 — 一歩先へ。 $x^2-x+1$ は円分多項式 ${\Phi }_6$ で、根は $1$ の原始 $6$ 乗根。$x^n$ を割った余りは $n\mathrm{mod}6$ で周期的に $1,x,x-1,-1,-x,-x+1$ と巡回する。割る式が $1$ の原始 $m$ 乗根の式なら周期 $m$。整数の合同 $\mathrm{mod}m$ とそっくりの構造が、多項式の割り算に現れる。

別解

別解 — $\omega$(1の原始 $6$ 乗根)を代入して余りを決める(得意な人向けの視点)。 $x^2-x+1=0$ の解を $\omega$ とすると、$\omega$ は $1$ の原始 $6$ 乗根(${\omega }^6=1$、${\omega }^3=-1$)。余りを $ax+b$ とおくと、$x=\omega$ で

$${\omega }^{2024}=a\omega +b.$$

$2024=6\cdot 337+2$ より ${\omega }^{2024}={\omega }^2$。そして ${\omega }^2=\omega -1$(${\omega }^2-\omega +1=0$ から)。だから

$$a\omega +b=\omega -1.$$

$\omega$ は虚数(実数でない)だから、係数を比べて $a=1$、$b=-1$。余りは $x-1$。

次数を下げて指数計算する本解と同じ余り $x-1$。$\omega$ は虚数なので、$1$ つの複素数の等式が実質 $2$ 本(実部・虚部)の働きをし、$a,b$ が一度に決まる。$x^2-x+1$ の根が「$1$ の原始 $6$ 乗根」だと見抜くのが鍵で、周期 $6$ が指数 $2024$ を $2$ に畳む。