威威學長｜高一多項式系列
📚 系列總覽：高一多項式系列地圖｜➡️ 下一篇：牛頓假設法 vs 拉格朗日插值，誰是考場之王？
$x^{200}$ 除以 $x^2+x+1$，直接長除會留下很長一串計算。先觀察除式：乘上 $x-1$，剛好得到 $x^3-1$。
下面的 $\equiv\pmod{D(x)}$ 表示「除以 $D(x)$ 後餘式相同」。這裡的 $D(x)=x^2+x+1$：
$$x^3-1=(x-1)(x^2+x+1) \implies x^3 \equiv 1 \pmod{x^2+x+1}$$
然後把 $x^{200}$ 拆開：
$$x^{200}=(x^3)^{66}\cdot x^2 \equiv 1^{66}\cdot x^2=x^2 \pmod{x^2+x+1}$$
$x^2$ 跟除式一樣是二次，還不能當最後的餘式。再用 $x^2\equiv-x-1$ 降一次，才得到 $-x-1$。看到次方變小很容易就想停筆，這裡再多看一眼次數😅
那為什麼能拿 $1$ 替換 $x^3$，又拿 $-x-1$ 替換 $x^2$？我們把「餘式不變」這件事寫清楚。
「模除式」到底在比什麼
$x^2+x+1$ 沒有被我們當成處處等於 $0$ 的函數。這裡的「相同」是指餘式相同，正式名稱叫多項式同餘。
定義很樸素：如果兩個多項式相減之後能被 $D(x)=x^2+x+1$ 整除，我們就說它們「在模 $D(x)$ 下同餘」，記作 $f(x)\equiv g(x) \pmod{D(x)}$。
白話翻譯：這兩個多項式除以 $D(x)$ 之後，留下的餘式一模一樣。
先從 $D(x)$ 自己開始。它除以自己，餘式為 $0$，所以 $x^2+x+1\equiv0$。兩邊同減 $x+1$，得到：
$$x^2\equiv -x-1 \pmod{x^2+x+1}$$
$x^2$ 與 $-x-1$ 的差就是 $D(x)$，所以兩者餘式相同；這沒有宣稱它們對每個 $x$ 都相等。前面的 $x^2$ 就靠這一步降成一次。
同餘也能乘同一個多項式。把 $x^2+x+1\equiv0$ 兩邊乘上 $(x-1)$：
$$(x-1)(x^2+x+1)\equiv 0 \implies x^3-1\equiv 0 \implies x^3\equiv 1$$
同餘還能取非負整數次方：$A\equiv B$ 會推出 $A^n\equiv B^n$。因此 $x^{200}=(x^3)^{66}x^2\equiv1^{66}x^2=x^2$。
每次替換都只改掉 $D(x)$ 的倍數，所以餘式不變。這個理由與 $x$ 取哪一個數無關。
把同餘換回熟悉的除法等式
如果你還不習慣 $\equiv$，我們直接用二項式定理證明，看看被省略的部分去了哪裡。
從 $x^3-1=(x-1)D(x)$ 移項：
$$x^3=1+(x-1)D(x)$$
這句話本身就是在說：$x^3$ 除以 $D(x)$，商式是 $(x-1)$、餘式是 $1$。現在把 $x^{200}$ 硬展開：
$$x^{200}=\left[1+(x-1)D(x)\right]^{66}\cdot x^2$$
用二項式定理展開中括號：
$$\left[1+(x-1)D(x)\right]^{66}=1+\binom{66}{1}(x-1)D(x)+\binom{66}{2}(x-1)^2D(x)^2+\cdots$$
除了第一項的 $1$ 以外，剩下每一項都至少含一個 $D(x)$。把那一大坨統一叫做 $M(x)\cdot D(x)$，於是：
$$x^{200}=x^2+M(x)\cdot D(x)\cdot x^2=x^2+\left[x^2M(x)\right]\cdot D(x)$$
右邊已經分成 $D(x)$ 的倍數加上 $x^2$，但還沒滿足餘式的次數限制。再把 $x^2=D(x)+(-x-1)$ 代入，把多出來的一份 $D(x)$ 收進倍式裡：
$$x^{200}=-x-1+\left[x^2M(x)+1\right]\cdot D(x)$$
現在候選餘式 $-x-1$ 的次數小於 $2$，而差又確實是 $D(x)$ 的倍數，兩個條件都檢查到了。商式不用整串展開，照樣能確認餘式，這才省掉那一大段計算🙂
這一招在大學的名字：理想與商環
在抽象代數裡，所有 $D(x)$ 的多項式倍數所成的集合叫做理想（ideal）。把「除以 $D(x)$ 後餘式相同」的多項式分為同一組，每組叫等價類；這些等價類可以做加法、乘法，形成商環。在商環裡，$D(x)$ 和 $0$ 代表同一個等價類，但原來的兩個多項式並沒有因此處處相等。
高一做這類題目，先掌握「差是除式的倍數」就夠了。以後讀到 $\mathbb{R}[x]/\langle x^2+x+1\rangle$，可以把它接回這個餘式分組的例子。
換你動手
練習 1：求 $x^{100}$ 除以 $x^2+x+1$ 的餘式。
點開看詳解
$100=3\times 33+1$，所以 $x^{100}=(x^3)^{33}\cdot x\equiv x$。
餘式：$x$（次數 $1<2$ ✓）。
這題在提醒你：拆完之後記得看剩下幾次方，$100\div 3$ 餘 $1$，尾巴就帶一個 $x$。
練習 2：求 $x^{50}+x^{25}$ 除以 $x^2-x+1$ 的餘式。
點開看詳解
這次除式換人做了。先找它跟三次方的關係：$(x+1)(x^2-x+1)=x^3+1$，所以 $x^3\equiv -1 \pmod{x^2-x+1}$。
$50=3\times 16+2$：$x^{50}=(x^3)^{16}\cdot x^2\equiv x^2$。
$25=3\times 8+1$：$x^{25}=(x^3)^{8}\cdot x\equiv x$。
合起來 $x^{50}+x^{25}\equiv x^2+x$。次數 $2$ 沒有小於除式的 $2$，還不合格，再用 $x^2\equiv x-1$ 降一次：
$$x^2+x\equiv (x-1)+x=2x-1$$
餘式：$2x-1$。
注意喔，這題最後一定要再檢查次數。除式二次，餘式最高只能一次，很多人栽在這最後一步。
練習 3（進階）：已知 $f(x)$ 除以 $x-2$ 餘 $5$，除以 $x+1$ 餘 $-4$，求 $f(x)$ 除以 $x^2-x-2$ 的餘式。
點開看詳解
$x^2-x-2=(x-2)(x+1)$，除式是這兩個一次式的乘積，所以餘式最高一次，設成 $ax+b$。
$f(2)=5$、$f(-1)=-4$（餘式定理直接翻譯條件），代入餘式：
$2a+b=5$，$-a+b=-4$。兩式相減得 $3a=9$，$a=3$，代回得 $b=-1$。
餘式：$3x-1$。
這題用兩個不同輸入值決定一次餘式；除式若再多一個不同的一次因式，就可以用三個值找二次以下的餘式。
若除式能拆成幾個不同的一次因式，也可以利用各根上的函數值找餘式。下一篇的插值法會沿著這條路繼續算。
不過在那之前，先確認你這招是真的會了：拿一張紙，把 $x^{99}$、$x^{100}$、$x^{101}$ 除以 $x^2+x+1$ 各算一次，只用同餘那三條規則，不用長除法。算完只檢查一件事：三個餘式的次數是不是都小於 $2$。如果有哪一個還是二次的，你就是漏了最後那一次降次，把算式貼給我，我們對一下。
