2017年8月21日 星期一

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$。

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



沒有留言:

張貼留言