2017-08-21多項式問題：求餘式

==問題==
求$(x^4 -x^3 +x)(x^3 + x^2 +x+1)$除以$x^2 +x+1$的餘式。

==解答==

本題做法很多種。

第一種方法是直接將被除式$(x^4 -x^3 +x)(x^3 + x^2 +x+1)$展開化簡，然後直接用長除法求解。

非常地暴力野蠻，計算量極大，在考試時，只在山窮水盡才這樣幹。

第二種方法是使用「除法原理」。由於除式$x^2 +x+1$為2次式，所以根據除法原理，可以假設餘式為$ax+b$，然後商式為$q(x)$，也就是有
$$
(x^4 -x^3 +x)(x^3 + x^2 +x+1) \div x^2 +x+1 = q(x)...ax+b.
$$
然後
$$
(x^4 -x^3 +x)(x^3 + x^2 +x+1) = (x^2+x+1) \cdot q(x) + (ax+b).
$$
接著，由於$x^2+x+1 = \left( x - \frac{-1 + \sqrt{3}i}{2} \right) \left( x - \frac{-1 - \sqrt{3}i}{2} \right)$(此因式分解其實係由直接解出方程式$x^2+x+1=0$所得)，若命$\omega_1 = \frac{-1 + \sqrt{3}i}{2}, \omega_2 = \frac{-1 - \sqrt{3}i}{2}$，將$\omega_1, \omega_2$依序帶入$(x^4 -x^3 +x)(x^3 + x^2 +x+1) = (x^2+x+1) \cdot q(x) + (ax+b)$可得關於$a$與$b$的聯立方程組，而後再解出$a, b$即得所求餘式。

這解法乍看好像頭頭是道，引經據典，很有數學味。但這解法有兩處不好難點，一是關於除式$x^2 +x+1$的因式分解並不直觀，係在複系數多項式環$\mathbb{C}[x]$上才能進行，不好算；另一是即使因式分解難不倒你，但最末帶入$\omega_1$與$\omega_2$時好計算嗎？我想不是那麼輕鬆的。

現在來談談第三種方法：多項式的同餘。

首先留意$x^3-1 = (x-1)(x^2+x+1)$，所以$x^3-1$是除式$x^2+x+1$的倍式。但如果僅考慮$x^3$，它與$x^3-1$就差在有無減1，所以可以看出$x^3$除以$x^2+x+1$後，餘式為1。

如果用同餘的記號，就有
$$
x^3 \equiv 1 \mod x^2+x+1.
$$
於是乎
\begin{eqnarray*}
& & (x^4 -x^3 +x)(x^3 + x^2 +x+1) \\
&=& (x^3 \cdot x -x^3 +x)[x^3+(x^2 +x+1)] \\
& \equiv & (1 \cdot x - 1 + x)[1+(0)] \mod x^2+x+1 \\
& \equiv & 2x-1 \mod x^2+x+1
\end{eqnarray*}
故答案為$2x-1$。

如果知曉多項式的同餘概念，那麼在處理餘式問題時有時會有更簡潔的解法。