41408 商式定理

終極密碼

遊戲規則:本遊戲為猜密碼的遊戲。密碼為0到100之間的其中1個整數,電腦會提示密碼的所在範圍,玩家必須在6次之內猜到密碼才能過關。

★ 終極密碼為0到100之間 ★
您共有六次機會

壹、前言

談到多項式除法, 大家都知道有所謂的「餘式定理」。 但是對於多項式除法所得的「商式」, 一般能想到的, 就是除法原理 $f(x)=g(x)\cdot Q(x)+R(x)$, 其中用符號代表的商式 $Q(x)$, 但 $Q(x)$ 有更具體的表達式嗎? 或者說, 商式的係數存在著特定的規律嗎? 經過一番探索之後, 發現在特定的條件下, 答案是肯定的。

在這篇文章中, 將從一個很基本的多項式除法出發, 使用完全齊次對稱多項式的性質, 將 $x^n$ 除以 $\prod\limits_{1\le i\le m} (x-p_i)$ 所得商式與餘式的係數, 完全用 $p_1,p_2,\ldots,p_m$ 來表達, 得到並證明所謂的「 多項式除法基本定理」 : 設 $p_1,p_2,\ldots,p_m$ 全相異, 且 $n\ge m\ge 2$, 則 $$x^n=\left[\prod_{1\le i\le m} (x-p_i)\right]\cdot \left[\sum_{j=0}^{n-m} h_j(p_1,p_2,\ldots,p_m)\cdot x^{n-m-j}\right] +\sum_{j=1}^m p_j^n \cdot\frac{\prod\limits_{1\le i\le m\atop i\not=j}(x-p_i)}{\prod\limits_{1\le i\le m\atop i\not=j}(p_j-p_i)}$$

特別地, 就商式的係數而言, 可得所謂的「 商式定理」 :

設 $p_1,p_2,\ldots,p_m$ 全相異, 且 $n\ge m\ge 2$, 則 $x^n$ 除以 $\prod\limits_{1\le i\le m}(x-p_i)$ 所得的商式的係數, 恰為 $p_1,p_2,\ldots,p_m$ 構成的「完全齊次對稱多項式」 $h_j(p_1,p_2,\ldots,p_m)$, 其中次數 $j$ 由 0 到 $n-m$。

貳、本文

一、定義、記號與已知公式:

1. 完全齊次對稱多項式 (Complete Homogeneous Symmetric Polynomial)

定義: $h_k(a_1,a_2,\ldots,a_n)=\sum\limits_{\lambda_1+\lambda_2+\cdots+\lambda_n=k\atop \lambda_1,\lambda_2,\ldots,\lambda_n\ge 0}(a_1^{\lambda_1}a_2^{\lambda_2} \cdots a_n^{\lambda_n})$, 稱為「變數 $a_1,a_2,\ldots,a_n$ 的 $k$ 次完全齊次對稱多項式」。 特別地, $h_0(a_1,a_2,\ldots,a_n)=1$, 且 $h_k(a)=a^k$。

例: $h_2(a_1,a_2,a_3)=\sum\limits_{\lambda_1+\lambda_2+\lambda_3=2\atop \lambda_1,\lambda_2,\lambda_3\ge 0}(a_1^{\lambda_1}a_2^{\lambda_2} a_3^{\lambda_3})=a_1^2+a_2^2+a_3^2+a_1a_2+a_2a_3+a_3a_1$ 。

例: $h_2(a,b,c)=a^2+b^2+c^2+ab+bc+ca$ 。

例: $h_3(a,b)=a^3+b^3+a^2b+ab^2$ 。

2. 拉格朗日插值型式

定義: $L_k(a_1,a_2,\ldots,a_n)=\sum\limits_{i=1}^n \dfrac{a_i^k}{\prod\limits_{1\le j\le n\atop j\not=i}(a_i-a_j)}$, 稱為「變數 $a_1,a_2,\ldots,a_n$ 的 $k$ 次拉格朗日插值型式」。

註: 以分子的次方來定義 $L$ 的下標。

例: \begin{eqnarray*} L_2(a_1,a_2,a_3)&=&\sum_{i=1}^3 \dfrac{a_i^2}{\prod\limits_{1\le j\le 3\atop j\not=i}(a_i-a_j)}\\ &=&\frac{a_1^2}{(a_1-a_2)(a_1-a_3)}+\frac{a_2^2}{(a_2-a_1)(a_2-a_3)}+\frac{a_3^2}{(a_3-a_1)(a_3-a_2)} \end{eqnarray*}

例: $$L_2(a,b,c)=\frac{a^2}{(a-b)(a-c)}+\frac{b^2}{(b-a)(b-c)}+\frac{c^2}{(c-a)(c-b)}$$

3. $h-L$ 轉換公式: $h_k(a_1,a_2,\ldots,a_n)=L_{k+n-1}(a_1,a_2,\ldots,a_n)$ (其中 $n\ge 2$, $k\ge 0$)

說明: 此一公式, 可將「完全齊次對稱多項式」與「拉格朗日插值型式」互相轉換。 以下舉例說明公式的精神與用法, 在附錄中證明 $L_3(a,b,c)=h_1(a,b,c)$ 供讀者參考, 而詳細證明請見參考資料

例: $$L_{k+1}(a,b)=\frac{a^{k+1}}{a-b}+\frac{b^{k+1}}{b-a}=\frac{a^{k+1}-b^{k+1}}{a-b}=a^k+a^{k-1}b+\cdots+ab^{k-1}+b^k=h_k(a,b),$$ 此為 $n=2$ 的情形。

例: 對於 $$L_6(a,b,c)=\frac{a^6}{(a-b)(a-c)}+\frac{b^6}{(b-a)(b-c)}+\frac{c^6}{(c-a)(c-b)},$$ 有 3 個變數 $a,b,c$, 先看出 $n=3$。 再由 $k+(n-1)=6$, 得 $k=4$。 於是有 $L_6(a,b,c)=h_4(a,b,c)$。 也可以這樣看, $\dfrac{a^6}{(a-b)(a-c)}$ 的 分母的次方之所以是 2, 是因為變數個數為 3, 用 $a$ 分別去減 $b,c$ 所產生。 而整個分式化簡之後所得齊次式的次數為 4, 可看成用分子的 6 次方, 減去分母的 2 次方而得。

再舉一例, 對於 \begin{eqnarray*} L_9(a,b,c,d)&=&\frac{a^9}{(a\!-\!b)(a\!-\!c)(a\!-\!d)}\!+\!\frac{b^9}{(b\!-\!a)(b\!-\!c)(b\!-\!d)}+\frac{c^9}{(c\!-\!a)(c\!-\!b)(c\!-\!d)}\\ &&+\frac{d^9}{(d\!-\!a)(d\!-\!b)(d\!-\!c)},\end{eqnarray*} 首先, 有 4 個變數 $a,b,c,d$, 則 $n=4$。 接著, $\dfrac{a^9}{(a\!-\!b)(a\!-\!c)(a\!-\!d)}$ 的分母的次方是 3, 分子的次方是 9, 所以化簡後所得齊次式的次數為 $9-3=6$, 於是有 $L_9(a,b,c,d)=h_6(a,b,c,d)$。 也就是說, $L$ 與 $h$ 的下標之差, 恰為變數個數減 1。

一般地, 對於 $L_{k+n-1}(a_1,a_2,\ldots,a_n)=\sum\limits_{i=1}^n \dfrac{a_i^{k+n-1}}{\prod\limits_{1\le j\le n\atop j\not=i}(a_i-a_j)}$, 有 $n$ 個變數 $a_1,a_2,\ldots,a_n$。 $\dfrac{a_i^{k+n-1}}{\prod\limits_{1\le j\le n\atop j\not=i}(a_i-a_j)}$ 的分母的次方是 $n-1$, 分子的次方是 $k+(n-1)$, 相減所得的 $k$, 即為化簡後所得的齊次式的次數, 即 $L_{k+n-1}(a_1,a_2,\ldots$, $a_n)=h_k(a_1,a_2,\ldots, a_n)$。

由於 $L$ 與 $h$ 的下標之差, 恰為變數個數減 1, 因此 $h-L$ 轉換公式, 也可寫成: $$L_k(a_1,a_2,\ldots,a_n)=h_{k-(n-1)}(a_1,a_2,\ldots,a_n)$$

例: $L_9(a,b,c,d)=h_{9-(4-1)}(a,b,c,d)=h_6(a,b,c,d)$ 。

在本篇文章的主要工作中, 用到 $h-L$ 轉換公式的情形:

  1. $L_k(a,b,c)=h_{k-2}(a,b,c)$(於第6頁)
  2. $L_n(p_1,p_2,\ldots,p_m,x)=h_{n-m}(p_1,p_2,\ldots,p_m,x)$
    $(L_n(p_1,p_2,\ldots,p_m,x)$ 有 $m+1$ 個變數 $p_1,p_2,\ldots,p_m,x$, $L$ 的下標為 $n$,
    則 $h$ 的下標為 $n-(m+1-1))=n-m)$ (於第7頁)
  3. $L_{n+4}(\alpha,\beta,\gamma)=h_{n+2}(\alpha,\beta,\gamma)$(於第9頁)

4. 基本對稱多項式

定義: $e_k(a_1,a_2,\ldots,a_n)=\sum\limits_{\lambda_1+\lambda_2+\cdots+\lambda_n=k\atop 0\le \lambda_1,\lambda_2,\ldots,\lambda_n\le 1} (a_1^{\lambda_1}a_2^{\lambda_2}\cdots a_n^{\lambda_n})$, 稱為「變數 $a_1,a_2,\ldots,a_n$ 的 $k$ 次基本對稱多項式」。

例: $e_2(a_1,a_2,a_3)=\sum\limits_{\lambda_1+\lambda_2+\lambda_3=2\atop 0\le \lambda_1,\lambda_2,\lambda_3\le 1} (a_1^{\lambda_1}a_2^{\lambda_2} a_3^{\lambda_3})=a_1a_2+a_2a_3+a_3a_1$。

例: $e_0(a,b,c)=1$, $e_1(a,b,c)=a+b+c$, $e_2(a,b,c)=ab+bc+ca$, $e_3(a,b,c)=abc$。

例: $(x-a)(x-b)(x-c)=x^3-e_1(a,b,c)x^2+e_2(a,b,c)x-e_3(a,b,c)$。

二、探索過程:

1. 從 $x^n=(x-a)(x^{n-1}+ax^{n-2}+\cdots+a^{n-2}x+a^{n-1})+a^n$ 出發, 有: \begin{eqnarray} x^n&=&(x-a)(x^{n-1}+ax^{n-2}+\cdots+a^{n-2}x+a^{n-1})+a^n\qquad~\label{1}\\ x^n&=&(x-b)(x^{n-1}+bx^{n-2}+\cdots+b^{n-2}x+b^{n-1})+b^n\label{2} \end{eqnarray} 設 $a\not=b$, 將 $(1)\times \dfrac{x-b}{a-b}+(2)\times \dfrac{x-a}{b-a}$,

可得等號的左邊為 $x^n\cdot\Big(\dfrac{x-b}{a-b}+\dfrac{x-a}{b-a}\Big)=x^n\cdot 1=x^n$

而等號的右邊為 \begin{eqnarray*} &&\hskip -20pt (x\!-\!a)(x\!-\!b)\Big(\frac{1}{a\!-\!b}x^{n-1}\!+\!\frac{a}{a\!-\!b}x^{n-2}+\frac{a^2}{a\!-\!b}x^{n-3}+\cdots\!+\!\frac{a^{n-2}}{a\!-\!b}x\!+\!\frac{a^{n-1}}{a\!-\!b}\Big)+ a^n\!\cdot\! \frac{x-b}{a\!-\!b}\\ &&\hskip -20pt +(x\!-\!b)(x\!-\!a)\Big(\frac{1}{b\!-\!a}x^{n-1}\!+\!\frac{b}{b\!-\!a}x^{n-2}+\frac{b^2}{b\!-\!a}x^{n-3}+\cdots\!+\!\frac{b^{n-2}}{b\!-\!a}x\!+\!\frac{b^{n-1}}{b\!-\!a}\Big)+ b^n\!\cdot\! \frac{x\!-\!a}{b\!-\!a}\\ &=&(x\!-\!a)(x\!-\!b)\Big(\frac{a\!-\!b}{a\!-\!b}x^{n-2}\!+\!\frac{a^2\!-\!b^2}{a\!-\!b}x^{n-3}\!+\!\cdots\!+\!\frac{a^{n-2}\!-\!b^{n-2}} {a\!-\!b}x\!+\!\frac{a^{n-1}-b^{n-1}}{a\!-\!b}\Big)\\ &&+\Big(a^n \cdot\frac{x\!-\!b}{a\!-\!b}+b^n\cdot\frac{x\!-\!a}{b\!-\!a}\Big)\\ &=&(x\!-\!a)(x\!-\!b)\Big[x^{n-2}+(a\!+\!b)x^{n-3}+\cdots+(a^{n-2}+a^{n-3}b+\cdots+b^{n-2})\Big]\\ &&+\Big(a^n \cdot\frac{x\!-\!b}{a\!-\!b}+b^n\cdot\frac{x\!-\!a}{b\!-\!a}\Big)\\ &=&(x\!-\!a)(x\!-\!b)\Big[h_0(a,b)x^{n-2}+h_1(a,b)x^{n-3}+\cdots+h_{n-3}(a,b)x+h_{n-2}(a,b)\Big]\\ &&+\Big(a^n \cdot\frac{x\!-\!b}{a\!-\!b}+b^n\cdot\frac{x\!-\!a}{b\!-\!a}\Big) \end{eqnarray*} 至此, 可得 \begin{eqnarray*} x^n&=&(x - a)(x - b)\Big[h_0(a,b)x^{n-2}+h_1(a,b)x^{n-3}+\cdots+h_{n-2}(a,b)\Big]\\ &&+\Big(a^n \cdot\frac{x - b}{a - b}+b^n\cdot\frac{x - a}{b - a}\Big).\end{eqnarray*}

註: 上式相當於 \begin{eqnarray*} x^n&=&(x - a)(x - b)\Big(\frac{a - b}{a - b}x^{n-2} + \frac{a^2 - b^2}{a - b}x^{n-3} + \cdots + \frac{a^{n-1}-b^{n-1}}{a - b}\Big)\\ &&+\frac{a^n - b^n}{a - b}x-(ab)\cdot\Big(\frac{a^{n-1}-b^{n-1}}{a - b}\Big)\end{eqnarray*} 在上式中, 以 $a=\dfrac{1+\sqrt 5}{2}$ 與 $b=\dfrac{1-\sqrt 5}{2}$ 代入, 由費氏數列的 Binet 公式, 可得

$x^n=(x^2-x-1)\cdot(F_1x^{n-2}+F_2x^{n-3}+\cdots+F_{n-2}x+F_{n-1})+F_n x+F_{n-1}$, 此式說明了 $x^n$ 除以 $x^2-x-1$ 所得的商式係數, 恰為著名的費氏數列。

2. 從 $x^n=(x-a)(x^{n-1}+ax^{n-2}+\cdots+a^{n-2}x+a^{n-1})+a^n$ 出發, 有: \begin{eqnarray*} x^n&=&(x-a)(x^{n-1}+ax^{n-2}+\cdots+a^{n-2}x+a^{n-1})+a^n(1)\\ x^n&=&(x-b)(x^{n-1}+bx^{n-2}+\cdots+b^{n-2}x+b^{n-1})+b^n(2)\\ x^n&=&(x-c)(x^{n-1}+cx^{n-2}+\cdots+c^{n-2}x+c^{n-1})+c^n(3) \end{eqnarray*} 設 $a,b,c$ 全相異, 將 $(1)\times \dfrac{(x-b)(x-c)}{(a-b)(a-c)}+(2)\times \dfrac{(x-a)(x-c)}{(b-a)(b-c)} +(3)\times \dfrac{(x-a)(x-b)}{(c-a)(c-b)} $,

可得等號的左邊為 $x^n\cdot\Big[\dfrac{(x\!-\!b)(x\!-\!c)}{(a\!-\!b)(a\!-\!c)}\!+\!\dfrac{(x\!-\!a)(x\!-\!c)}{(b\!-\!a)(b\!-\!c)} \!+\!\dfrac{(x\!-\!a)(x\!-\!b)}{(c\!-\!a)(c\!-\!b)}\Big]\!=\!x^n\cdot 1\!=\!x^n$, (註1)

而等號的右邊為 \begin{eqnarray*} &&\hskip -10pt (x\!-\!a)(x\!-\!b)(x\!-\!c)\Big(\frac 1{(a\!-\!b)(a\!-\!c)}x^{n-1}+\frac a{(a\!-\!b)(a\!-\!c)}x^{n-2}+\cdots +\frac {a^{n-1}}{(a\!-\!b)(a\!-\!c)}\Big)\\ &&+a^n \dfrac{(x\!-\!b)(x\!-\!c)}{(a\!-\!b)(a\!-\!c)}+(x\!-\!b)(x\!-\!a)(x\!-\!c)\Big(\frac 1{(b\!-\!a)(b\!-\!c)}x^{n-1}+\frac b{(b\!-\!a)(b\!-\!c)}x^{n-2} +\cdots\\ &&+\frac {b^{n-1}}{(b\!-\!a)(b\!-\!c)}\Big)+b^n \dfrac{(x\!-\!a)(x\!-\!c)}{(b\!-\!a)(b\!-\!c)} +(x\!-\!c)(x\!-\!a)(x\!-\!b)\Big(\frac 1{(c\!-\!a)(c\!-\!b)}x^{n-1}\\ &&+\frac c{(c\!-\!a)(c\!-\!b)}x^{n-2} +\cdots+\frac {c^{n-1}}{(c\!-\!a)(c\!-\!b)}\Big)+c^n \dfrac{(x\!-\!a)(x\!-\!b)}{(c\!-\!a)(c\!-\!b)}\\ &=&(x\!-\!a)(x\!-\!b)(x\!-\!c)\Big[L_2(a,b,c)x^{n-3}+L_3(a,b,c)x^{n-4}+\cdots+L_{n-2}(a,b,c)x\\ &&+L_{n-1}(a,b,c)\Big] +a^n \dfrac{(x\!-\!b)(x\!-\!c)}{(a\!-\!b)(a\!-\!c)}+b^n \dfrac{(x\!-\!a)(x\!-\!c)}{(b\!-\!a)(b\!-\!c)}+c^n \dfrac{(x\!-\!a)(x\!-\!b)}{(c\!-\!a)(c\!-\!b)} \hskip 1cm\hbox{(註2)}\\ &=&(x\!-\!a)(x\!-\!b)(x\!-\!c)\Big[h_0(a,b,c)x^{n-3}+h_1(a,b,c)x^{n-4}+\cdots+h_{n-4}(a,b,c)x\\ &&+h_{n-3}(a,b,c)\Big]+a^n \dfrac{(x\!-\!b)(x\!-\!c)}{(a\!-\!b)(a\!-\!c)}\!+\!b^n \dfrac{(x\!-\!a)(x\!-\!c)}{(b\!-\!a)(b\!-\!c)} \!+\!c^n \dfrac{(x\!-\!a)(x\!-\!b)}{(c\!-\!a)(c\!-\!b)}\\ &&\hskip 7.4cm(\because\ L_k(a,b,c)\!=\!h_{k-2}(a,b,c)) \end{eqnarray*} 至此, 可得 \begin{eqnarray*} x^n&=&(x\!-\!a)(x\!-\!b)(x\!-\!c)\Big[h_0(a,b,c)x^{n-3}+h_1(a,b,c)x^{n-4}+\cdots+h_{n-4}(a,b,c)x\\ &&+h_{n-3}(a,b,c)\Big]+a^n \dfrac{(x\!-\!b)(x\!-\!c)}{(a\!-\!b)(a\!-\!c)}\!+\!b^n \dfrac{(x\!-\!a)(x\!-\!c)}{(b\!-\!a)(b\!-\!c)} \!+\!c^n \dfrac{(x\!-\!a)(x\!-\!b)}{(c\!-\!a)(c\!-\!b)}. \end{eqnarray*}

意義: 由此式可知, $x^n$ 除以 $(x\!-\!a)(x\!-\!b)(x\!-\!c)$ 的商式係數, 正是 $a,b,c$ 三變數構成的「完全齊次對稱多項式」 $h_j(a,b,c)$, 其中次數 $j$ 由 0 到 $n-3$。

註1: 將 $\dfrac{(x\!-\!b)(x\!-\!c)}{(a\!-\!b)(a\!-\!c)}\!+\!\dfrac{(x\!-\!a)(x\!-\!c)}{(b\!-\!a)(b\!-\!c)} \!+\!\dfrac{(x\!-\!a)(x\!-\!b)}{(c\!-\!a)(c\!-\!b)}=1$ 之證明置於附錄。

註2: 將 $L_0(a,b,c)= \dfrac 1{(a\!-\!b)(a\!-\!c)}+\dfrac 1{(b\!-\!a)(b\!-\!c)}+\dfrac 1{(c\!-\!a)(c\!-\!b)}=0$ 與 $L_1(a,b,c)= \dfrac a{(a\!-\!b)(a\!-\!c)}+\dfrac b{(b\!-\!a)(b\!-\!c)}+\dfrac c{(c\!-\!a)(c\!-\!b)}=0$ 之證明置於附錄。

三、主要定理:

由以上的探索過程, 歸納可得以下的定理:

多項式除法基本定理: 設 $p_1,p_2,\ldots,p_m$ 全相異, 且 $n\ge m\ge 2$, 則 $$x^n=\left[\prod_{1\le i\le m}(x-p_i)\right]\left[\sum_{j=0}^{n-m} h_j(p_1,p_2,\ldots,p_m)x^{n-m-j}\right]+\sum_{j=1}^m p_j^n \dfrac{\prod\limits_{1\le i\le m\atop i\not= j}(x-p_i)}{\prod\limits_{1\le i\le m\atop i\not= j}(p_j-p_i)}.$$

證明: \begin{eqnarray*} &&\hskip -20pt \dfrac{x^n-\sum\limits_{j=1}^m p_j^n \dfrac{\prod\limits_{1\le i\le m\atop i\not= j}(x-p_i)}{\prod\limits_{1\le i\le m\atop i\not= j}(p_j-p_i)}}{\prod\limits_{1\le i\le m}(x-p_i)} =\dfrac{x^n}{\prod\limits_{1\le i\le m}(x-p_i)}-\sum\limits_{j=1}^m p_j^n \dfrac{\left(\dfrac{\prod\limits_{1\le i\le m\atop i\not= j}(x-p_i)}{\prod\limits_{1\le i\le m}(x-p_i)}\right)}{\prod\limits_{1\le i\le m \atop i\not= j}(p_j-p_i)}\\ &=&\dfrac{x^n}{\prod\limits_{1\le i\le m}(x-p_i)}+\sum\limits_{j=1}^m \dfrac{p_j^n}{\prod\limits_{1\le i\le m \atop i\not= j}(p_j-p_i)(p_j-x)}=L_n(p_1,p_2,\ldots,p_m,x)\\ &=&h_{n-(m+1-1)}(p_1,p_2,\ldots,p_m,x)\qquad \hbox{(由 $h-L$ 轉換公式)}\\ &=&\sum_{j=0}^{n-m}h_j(p_1,p_2,\ldots,p_m)x^{n-m-j}\qquad \hbox{(將齊次式按照 $x$ 的次方降冪展開)}\\ \Rightarrow\ x^n&\!=\!&\left[\prod_{1\le i\le m}(x\!-\!p_i)\right]\left[\sum_{j=0}^{n-m} h_j(p_1,p_2,\ldots,p_m)x^{n-m-j}\right]\!+\!\!\sum_{j=1}^m p_j^n \dfrac{\prod\limits_{1\le i\le m\atop i\not= j}(x\!-\!p_i)}{\prod\limits_{1\le i\le m\atop i\not= j}(p_j\!-\!p_i)},\hbox{得證。} \end{eqnarray*}

意義: $x^n$ 除以 $\prod\limits_{1\le i\le m}(x\!-\!p_i)$ 的商式為 $\sum\limits_{j=0}^{n-m} h_j(p_1,p_2,\ldots,p_m)x^{n-m-j}$, 餘式為
$\sum\limits_{j=1}^m p_j^n \dfrac{\prod\limits_{1\le i\le m\atop i\not= j}(x\!-\!p_i)}{\prod\limits_{1\le i\le m\atop i\not= j}(p_j\!-\!p_i)}$, 此式將 $x^n$ 除以 $\prod\limits_{1\le i\le m}(x-p_i)$ 所得商式與餘式的係數, 完全用 $p_1,p_2,\ldots$, $p_m$ 來表達, 刻劃了多項式除法的內在架構, 故稱之為「 多項式除法基本定理」。

特別地, 只著眼於商式的係數時, 可得所謂的「 商式定理」 :

商式定理: 設 $p_1,p_2,\ldots,p_m$ 全相異, 且 $n\ge m\ge 2$, 則 $x^n$ 除以 $\prod\limits_{1\le i\le m} (x-p_i)$ 所得的商式的係數, 恰為 $p_1,p_2,\ldots,p_m$ 構成的「完全齊次對稱多項式」 $h_j(p_1,p_2,\ldots,p_m)$, 次數 $j$ 由 0 到 $n-m$。

四、應用:

(一) 對稱多項式的 $e-h$ 恆等式

將 $$x^n=\left[\prod_{1\le i\le m}(x\!-\!p_i)\right]\left[\sum_{j=0}^{n-m} h_j(p_1,p_2,\ldots,p_m)x^{n-m-j}\right]\!+\!\!\sum_{j=1}^m p_j^n \dfrac{\prod\limits_{1\le i\le m\atop i\not= j}(x\!-\!p_i)}{\prod\limits_{1\le i\le m\atop i\not= j}(p_j\!-\!p_i)}$$ 一式改寫成等價的 $x^n=(x^m-e_1x^{m-1}+\cdots+(-1)^ke_kx^{m-k}+\cdots+(-1)^me_m) (h_0x^{n-m}+h_1x^{n-m-1}+\cdots+h_kx^{n-m-k}+\cdots+h_{n-m-1}x+h_{n-m})+R(x)$, 其中 $$R(x)=\sum_{j=1}^m p_j^n \dfrac{\prod\limits_{1\le i\le m\atop i\not= j}(x\!-\!p_i)}{\prod\limits_{1\le i\le m\atop i\not= j}(p_j\!-\!p_i)}$$ $\Rightarrow {\rm deg}\, R(x)\le m-1$ 。 (註1)

設 $m$ 為定數, 取 $n\ge 2m$, 比較式子等號兩邊 $x^m$ 的係數, 則等號左邊是 0 ($\because\ n\ge 2m\gt m$), $$\hbox{右邊是 }\ h_{n-m}-e_1h_{n-m-1}+\cdots+(-1)^ke_kh_{n-m-k}+\cdots+(-1)^m e_mh_{n-2m},$$ 即得對所有固定的 $m$, 當 $n\ge 2m$ 時, $$h_{n-m}-e_1h_{n-m-1}+\cdots+(-1)^ke_kh_{n-m-k}+\cdots+(-1)^m e_mh_{n-2m}=0$$ 恆成立。 令 $N=n-m$, 則 $n\ge 2m\Leftrightarrow N\ge m$, 依此可將上述事實寫成:

對所有固定的 $m$, 當 $N\ge m$ 時, $$h_{N}-e_1h_{N-1}+\cdots+(-1)^ke_kh_{N-k}+\cdots+(-1)^m e_mh_{N-m}=0$$ 恆成立。 亦即對所有固定的 $m$, 當 $N\ge m$ 時, $\sum\limits_{k=0}^m (-1)^ke_kh_{N-k}=0$ 恆成立。

此恆等式刻畫了 基本對稱多項式 $e_k$ 與完全齊次對稱多項式 $h_k$ 的關聯性。 另外,$\sum\limits_{k=0}^m (-1)^ke_kh_{N-k}=0$ 也說明了 $\langle h_n\rangle$ 構成一個 $m$ 階遞迴數列。

例: 當 $m=3$ 時, 有 $h_N-e_1h_{N-1}+e_2h_{N-2}-e_3h_{N-3}=0$, 對 $N\ge 3$ 皆成立。 (註2)

註1: 此處用 $e_k$ 表示 $e_k(p_1,p_2,\ldots,p_m)$, 用 $h_k$ 表示 $h_k(p_1,p_2,\ldots,p_m)$。

註2: 此處用 $h_k$ 表示 $h_k(p_1,p_2,p_3)$。

{(二) Padovan 數列(巴都萬數列)}

定義 Padovan 數列 $\langle P_n\rangle:\ \left\{ \begin{array}{l} P_0=P_1=P_2=1\\[5pt] P_n=P_{n-2}+P_{n-3}\end{array} \right.$。 (參考資料 )

數列的前幾項為 1, 1, 1, 2, 2, 3, 4, 5, 7, $\cdots$ 。

設其特徵方程式 $x^3-x-1=0$ 的三根為 $\alpha,\beta,\gamma$, 由參考資料 , 知數列的一般項為 $$P_n=\frac{(1-\beta)(1-\gamma)}{(\alpha-\beta)(\alpha-\gamma)}\alpha^n+\frac{(1-\alpha)(1-\gamma)}{(\beta-\alpha)(\beta-\gamma)}\beta^n +\frac{(1-\alpha)(1-\beta)}{(\gamma-\beta)(\gamma-\alpha)}\gamma^n.$$ 本文在此給出 $P_n$ 一般項的另一個表達式: $$P_n=\frac{1}{(\alpha-\beta)(\alpha-\gamma)}\alpha^{n+4}+\frac{1}{(\beta-\alpha)(\beta-\gamma)}\beta^{n+4} +\frac{1}{(\gamma-\alpha)(\gamma-\beta)}\gamma^{n+4}.\quad\hbox{(證明見附錄)}$$

意義: 此一表達式將 $P_n$ 改寫成拉格朗日型式 $L_{n+4}(\alpha,\beta,\gamma)$, 由 $h-L$ 轉換公式, 可再變成 $h_{n+2}(\alpha,\beta,\gamma)$, 即 \begin{eqnarray*} P_n&=&\frac{1}{(\alpha-\beta)(\alpha-\gamma)}\alpha^{n+4}+\frac{1}{(\beta-\alpha)(\beta-\gamma)}\beta^{n+4} +\frac{1}{(\gamma-\alpha)(\gamma-\beta)}\gamma^{n+4}\\ &=&L_{n+4}(\alpha,\beta,\gamma)=h_{n+2}(\alpha,\beta,\gamma) \end{eqnarray*} 得到關係式: $P_n=h_{n+2}(\alpha,\beta,\gamma)$, 其中 $n\ge 0$, 即 Padovan 數列可用「完全齊次對稱多項式」表示。 此式也可寫成 $h_n(\alpha,\beta,\gamma)=P_{n-2}$, 其中 $n\ge 2$ 。

應用: 由商式定理, 取 $m=3$, 且 $p_1,p_2,p_3$ 分別為 $\alpha,\beta,\gamma$ (即 $x^3-x-1=0$ 的三根), 可得 \begin{eqnarray*} x^n&=&(x\!-\!\alpha)(x\!-\!\beta)(x\!-\!\gamma)[h_{0}(\alpha,\beta,\gamma)x^{n-3}+h_{1}(\alpha,\beta,\gamma)x^{n-4}+\cdots+h_{n-4}(\alpha,\beta,\gamma)x\\ &&+h_{n-3}(\alpha,\beta,\gamma)]+R(x), \end{eqnarray*} 其中 $R(x)$ 為 $x^n$ 除以 $(x-\alpha)(x-\beta)(x-\gamma)$ 所得的餘式。 於是有 $$x^n=(x^3-x-1)[P_{-2}x^{n-3}+P_{-1}x^{n-4}+P_0x^{n-4}+\cdots+P_{n-6}x+P_{n-5}]+R(x). \qquad\hbox{ (註)}$$ 此式說明了 當我們用 $x^n$ 除以 $x^3-x-1$ 時, 所得的商式係數, 恰好為 Padovan 數列。

例: 由長除法可得 $$x^{10}=(x^3-x-1)(1x^7+0x^6+1x^5+1x^4+1x^3+2x^2+2x+3)+4x^2+5x+3.$$

註: $P_{-1}$ 與 $P_{-2}$ 的值可由遞迴關係 $P_n=P_{n-2}+P_{n-3}$ 來決定。

例: 由 $P_2=P_0+P_{-1}$, 得 $P_{-1}=0$。 由 $P_1=P_{-1}+P_{-2}$, 得 $P_{-2}=1$ 。

參、結語

有「餘式定理」, 為何沒有「商式定理」? 相信部份讀者腦海也曾經閃過此一念頭。

本篇文章的出發點並非是要標新立異, 而是在探索之後, 發覺多項式除法實有其更深入的內在結構: 除法原理 $f(x)=g(x)\cdot Q(x)+R(x)$ 之中, 抽象而需用演算法一步步求出的商式 $Q(x)$, 在最根本的情形, 即 $x^n$ 除以 $\prod\limits_{1\le i\le m}(x-p_i)$, 其中 $p_1,p_2,\ldots, p_m$ 全相異, 此時 $Q(x)$ 可以用具體的公式 $h_j(p_1,p_2,\ldots,p_m)$ 加以表達, 特將此一事實, 命名為「 商式定理」。 當然, 此一命名是否恰當, 就有賴各位讀者作出判斷與指教了。

在多項式除法的過程中, 出現了人們熟知的費氏數列 (參考資料 ), 此一奇特現象, 背後有其必然性: 一方面, $x^n$ 除以 $\prod\limits_{1\le i\le m}(x-p_i)$ 的商式的係數, 構成數列 $\langle h_n\rangle$, 另一方面, 本文也證明了 $\langle h_n\rangle$ 是遞迴數列。 也就是說, 透過「商式定理」, 本文說明了 為何在多項式除法的過程中, 會出現遞迴數列。 相信除此之外, 「商式定理」應該可以有其他更有趣更有意義的應用, 筆者相當期待。

附錄

1. $L_3(a,b,c)=h_1(a,b,c)$

證明: \begin{eqnarray*} L_3(a,b,c)&\!=\!&\frac{a^3}{(a\!-\!b)(a\!-\!c)}\!+\!\frac{b^3}{(b\!-\!a)(b\!-\!c)}\!+\!\frac{c^3}{(c\!-\!a)(c\!-\!b)}\!=\! \frac{a^3(c\!-\!b) \!+\!b^3(a\!-\!c)\!+\!c^3(b\!-\!a)}{(c\!-\!b)(c\!-\!a)(b\!-\!a)}\\ &\!=\!&\frac{\left|\begin{array}{ccc} ~1~&~a~&~a^3~\\ 1&b&b^3\\ 1&c&c^3 \end{array}\right|}{(c\!-\!b)(c\!-\!a)(b\!-\!a)}=\frac{\left|\begin{array}{ccc} ~1~&~a~&~a^3~\\ 0&b\!-\!a&b^3\!-\!a^3\\ 0&c\!-\!a&c^3\!-\!a^3 \end{array}\right|}{(c\!-\!b)(c\!-\!a)(b\!-\!a)}=\frac{(b\!-\!a)(c\!-\!a)\left|\begin{array}{cc} ~1~&b^2+ba+a^2\\ ~1~&c^2+ca+a^2 \end{array}\right|}{(c\!-\!b)(c\!-\!a)(b\!-\!a)}\\ &\!=\!&\frac{(b\!-\!a)(c\!-\!a)[(c^2\!-\!b^2)+(c\!-\!b)a]}{(c\!-\!b)(c\!-\!a)(b\!-\!a)}=\frac{(b\!-\!a)(c\!-\!a)(c\!-\!b)(a+b+c)} {(c\!-\!b)(c\!-\!a)(b\!-\!a)}\\ &\!=\!&a+b+c=h_1(a,b,c) \end{eqnarray*} 2. $\dfrac{(x-b)(x-c)}{(a-b)(a-c)}+\dfrac{(x-a)(x-c)}{(b-a)(b-c)}+\dfrac{(x-a)(x-b)}{(c-a)(c-b)}=1$

證明: 令 \begin{eqnarray*} f(x)&=&\dfrac{(x-b)(x-c)}{(a-b)(a-c)}+\dfrac{(x-a)(x-c)}{(b-a)(b-c)}+\dfrac{(x-a)(x-b)}{(c-a)(c-b)}\Rightarrow f(a)=f(b)=f(c)=1\\ \because&& {\rm deg}\, f(x)\le 2\Rightarrow f(x)=1 \end{eqnarray*} 3. (1) $\dfrac{1}{(a-b)(a-c)}+\dfrac{1}{(b-a)(b-c)}+\dfrac{1}{(c-a)(c-b)}=0$

(2) $\dfrac{a}{(a-b)(a-c)}+\dfrac{b}{(b-a)(b-c)}+\dfrac{c}{(c-a)(c-b)}=0$

證明:

(1) $\dfrac{1}{(a-b)(a-c)}+\dfrac{1}{(b-a)(b-c)}+\dfrac{1}{(c-a)(c-b)}=\dfrac{(c\!-\!b)\!+\!(a\!-\!c)\!+\!(b\!-\!a)}{(c-a)(c-b)(b-a)}=0$

(2) $\dfrac{a}{(a-b)(a-c)}+\dfrac{b}{(b-a)(b-c)}+\dfrac{c}{(c-a)(c-b)}=\dfrac{a(c\!-\!b)\!+\!b(a\!-\!c)\!+\!c(b\!-\!a)}{(c-a)(c-b)(b-a)}=0$

4. $P_n=\dfrac{1}{(\alpha-\beta)(\alpha-\gamma)}\alpha^{n+4}+\dfrac{1}{(\beta-\alpha)(\beta-\gamma)}\beta^{n+4} +\dfrac{1}{(\gamma-\alpha)(\gamma-\beta)}\gamma^{n+4}$.

證明: 一方面, $x^3-x-1$ 的三根為 $\alpha,\beta,\gamma\Rightarrow x^3-x-1=(x-\alpha)(x-\beta)(x-\gamma)\Rightarrow (1-\alpha)(1-\beta)(1-\gamma)=1-1-1=-1$ $\Rightarrow (1-\beta)(1-\gamma)=\dfrac 1{\alpha-1}$

另一方面, 注意到 $x^5-x^4-1=(x^3-x-1)(x^2-x+1)$ (參考資料 )

$\Rightarrow \ \alpha^5-\alpha^4-1=(\alpha^3-\alpha-1)(\alpha^2-\alpha+1)=0$

$\Rightarrow \ \alpha^4(\alpha-1)=1$

$\Rightarrow \ \dfrac{1}{\alpha-1}=\alpha^4$

綜合以上討論, 可得 $(1-\beta)(1-\gamma)=\alpha^4$, 同理可證$(1-\alpha)(1-\gamma)=\beta^4$ 與 $(1-\alpha)(1-\beta)$ $=\gamma^4$, 可得 \begin{eqnarray*} P_n&=&\dfrac{(1-\beta)(1-\gamma)}{(\alpha-\beta)(\alpha-\gamma)}\alpha^{n}+\dfrac{(1-\alpha)(1-\gamma)}{(\beta-\alpha)(\beta-\gamma)}\beta^{n} +\dfrac{(1-\alpha)(1-\beta)}{(\gamma-\alpha)(\gamma-\beta)}\gamma^{n}\\ &=&\dfrac{1}{(\alpha-\beta)(\alpha-\gamma)}\alpha^{n+4}+\dfrac{1}{(\beta-\alpha)(\beta-\gamma)}\beta^{n+4} +\dfrac{1}{(\gamma-\alpha)(\gamma-\beta)}\gamma^{n+4},\qquad \hbox{ 得證。} \end{eqnarray*}

參考資料

陳建燁。 推廣的 Vandermonde 行列式(最右行升次型)。 高中數學學科中心電子報第 114 期。 廖信傑。 用矩陣方法探討三階遞迴數列。 數學傳播季刊, 38(1), 36-55, 2014。 mathworld.wolfram.com/PadovanSequence.html。 陳建燁。 多項式除法與遞迴數列。 高中數學學科中心電子報第108期。 陳建燁。 遞迴數列的「特徵多項式」與「線性衍生遞迴式」。 數學傳播季刊, 40(4), 57-62, 2016。

---本文作者任教台北市立第一女子高級中學---