[數論] 整值多項式 (Integer-valued Polynomial)

參考資料
張文忠，基礎數論：原理及題解，中央圖書，2002年出版，ISBN：978-957-637-493
數學研發論壇 http://bbs.emath.ac.cn/thread-2912-1-1.html
NEWTON FORWARD INTERPOLATION ON EQUISPACED POINTS
https://www3.nd.edu/~jjwteach/441/PdfNotes/lecture7.pdf
呂冠緯，高一上數學(第二章：多項式函數)
http://www.youtube.com/playlist?list=PLZruNYXiv2mC6Prcx7cWl064sU_0vA8Di

當變數 $x$ 取整數時，若多項式 $f(x)$ 的值恆為整數，則稱 $f(x)$ 為整值多項式。

整係數的多項式一定是整值多項式，但有沒有可能當係數非整數、$f(x)$ 的值卻都為整數呢？有的，例如當多項式是組合數(combination number)形式時，也就是說，

$\forall x\in \mathbb{Z},\; f(x)=\binom{x}{n}=\frac{x\cdot (x-1)\cdots (x-n+1)}{n!}\in \mathbb{Z},\; 0\leq n\leq x$.

定理12 一個 $n$ 次多項式 $f(x)$ 是整值多項式的充分必要條件是 $f(x)$ 可以寫成

$f(x)=C_{n}\binom{x}{n}+C_{n-1}\binom{x}{n-1}+\cdots +C_1\binom{x}{1}+C_0$，其中 $C_i,\; 0\leq i\leq k$ 皆為整數。

<pf>
必要性$(\Leftarrow )$
因為 $\binom{x}{n},\binom{x}{n-1},\cdots ,\binom{x}{1},1$ 皆為整值多項式。整值多項式分別乘上整數 $C_n,C_{n-1},\cdots ,C_0$ 後相加仍為整值多項式。

充分性$(\Rightarrow )$
任何一個 $n$ 次多項式必可寫成 $f(x)=C_{n}\binom{x}{n}+C_{n-1}\binom{x}{n-1}+\cdots +C_1\binom{x}{1}+C_0$ 的形式。現在要證明當 $f(x)$ 是整值多項式時，$C_i,\; 0\leq i\leq k$ 皆為整數。

我們記 $\Delta f(x)=f(x+1)-f(x)$(First order forward difference)。一般地有 $\Delta ^{r}f(x)=\Delta (\Delta ^{r-1}f(x))$。

則 $\Delta f(x)=f(x+1)-f(x)$
                $=C_n\left [ \binom{x+1}{n}-\binom{x}{n} \right ]+C_{n-1}\left [ \binom{x+1}{n-1}-\binom{x}{n-1} \right ]+\cdots +C_1\left [ \binom{x+1}{1}-\binom{x}{1} \right ]$
                $=C_n\binom{x}{n-1}+C_{n-1}\binom{x}{n-2}+\cdots +C_1$.

得到 $f(0)=C_0$
        $\Delta f(x)\mid_{x=0}=C_1$
        $\Delta ^2f(x)\mid_{x=0}=C_2$
           $\vdots$
        $\Delta ^nf(x)\mid_{x=0}=C_n$.

因為 $f(x)$ 是整值多項式，所以 $\Delta f(x),\; \Delta ^2f(x),\; \cdots ,\; \Delta ^nf(x)$ 也都是整值多項式。所以 $C_0$, $C1$, $\cdots$, $C_n$ 也都是整數。

定理14 設 $n$ 次多項式為 $f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0,\: (a_k\neq 0)$。若 $x$ 取 $n+1$ 個連續整數 $a,\; a+1,\cdots ,\; a+n$ 時，$f(x)$ 的值皆為整數，則 $f(x)$ 為整值多項式。

定理14' 設 $n$ 次多項式為 $f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0,\: (a_k\neq 0)$。若 $x$ 取 $n+1$ 個連續整數 $a,\; a+1,\cdots ,\; a+n$ 時，$f(x)$ 的值皆能被 $m$ 整除，則對任意 $x$，$m\mid f(x)$。

上面兩個定理可用牛頓插值公式或 Lagrange's interpolation formula 證明。牛頓插值公式也叫做牛頓級數，由「牛頓前向差分方程」的項組成。