[數論] 高次同餘式 (Polynomial Congruences)

參考資料
張文忠，基礎數論：原理及題解，中央圖書，2002年出版，ISBN：978-957-637-493
Polynomial Congruences 
http://www.cs.xu.edu/math/math302/04f/PolyCongruences.pdf
http://www2.latech.edu/~schroder/slides/number_theory/14_polynomial_congruences.pdf

在上一篇我們介紹並討論一次同餘式（組）的求解。本篇將討論關於高次同餘式的性質及求解方法。

一、高次同餘式介紹
一個典型的高次同餘式可表示為$$ f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots a_1x+a_0\equiv 0\; (\textrm{mod}\; m) , \textrm{where}\; a_i\in \mathbb{Z}, i=0,1,\cdots ,n$$
若模數 $m$ 是質數，我們可以透過質數的特性去探討同餘式之解的存在性及求解；若模數 $m$ 是合數，通常的處理方法是把該模數轉為質數模數加以研究。

若 $m_1, m_2,\cdots ,m_n$ 是 $n$ 個兩兩互質的正整數，$m=m_1m_2\cdots m_n$，則同餘方程式 $$f(x)\equiv 0\; (\textrm{mod}\; m)$$與同餘方程組 $$f(x)\equiv 0\; (\textrm{mod}\; m_i), \; i=1,2,\cdots n$$具有相同解。若用 $T_i$ 表示 $f(x)\equiv 0\; (\textrm{mod}\; m_i)$ 的解的個數，$T$ 表示 $f(x)\equiv 0\; (\textrm{mod}\; m)$ 的解的個數，則 $$T=T_1T_2\cdots T_n$$以下僅討論模數 $m$ 為質數的情況。

對於 $f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0\equiv 0$(mod $p$)，其中 $p$ 是質數，且 $p\nmid a_i$，$i=0,1,\cdots ,n$，求解的基本方法有二：

1. 將模 $p$ 的完全剩餘系 $\left \{ 0,1,\cdots ,p-1 \right \}$ 的元素逐一代入同餘式
此方法毋需其他特殊技巧，當 $p$ 很小的時候相當實用。但當 $p$ 很大的時候，使用此方法就顯得缺乏效率。

2. 降低原式的複雜度
2.1 降低 $f(x)$ 中的 $x^i$ 的係數，或是降低 $f(x)$ 的次數。

<例1> 求解同餘式 $x^{10}+^7-x^3+3\equiv 0$ (mod $5$)
<解1> 因為 $(x,5)=1$，由 Euler's theorem 知 $x^{\phi (5)}\equiv x^4\equiv 1$ (mod $5$)。故原式可化簡為 $$x^{10}+x^7-x^3+3\equiv x^2+x^3-x^3+3\equiv x^2+3 \equiv 0\; (\textrm{mod}\; 5)$$即原式與 $x^2+3 \equiv 0\; (\textrm{mod}\; 5)$ 有相同的解。

將模 $5$ 的完全剩餘系 $\left \{ 0,1,2,3,4 \right \}$ 元素逐一代入 $x^2+3 \equiv 0\; (\textrm{mod}\; 5)$ ，發現此同餘式無解，故原同餘式也無解。

2.2 利用因式分解
假設 $f(x)=q(x)g(x)\equiv 0\; (\textrm{mod}\; p)$，即 $q(x)\equiv 0\; (\textrm{mod}\; p)$，$p(x)\equiv 0\; (\textrm{mod}\; p)$。

2.3 $f(x)\equiv 0\; (\textrm{mod}\; p)$ 必與一個次數小於 $p$ 的質數模 $p$ 的同餘式有相同的解
若 $f(x)$ 的次數 $n< p$，結論顯然成立。

若 $f(x)$ 的次數 $n\geq p$，由多項式的帶餘式除法知，存在兩個整係數多項式 $q(x)$ 與 $r(x)$，使 $$f(x)=(x^p-x)\cdot q(x)+r(x)$$其中 $r(x)$ 的次數小於 $p$。

為何選擇 $x^p-x$ 作為除式？由費馬小定理，易知 $x^p-x$ 可以被 $p$ 整除，所以$$f(x)=(x^p-x)\cdot q(x)+r(x)\equiv r(x)\; (\textrm{mod}\; p)$$也就是說，$f(x)\equiv 0\; (\textrm{mod}\; p)$ 與 $r(x)\equiv 0\; (\textrm{mod}\; p)$ 同解。


二、Lagrange定理
定義：設 $p$ 是質數，且 $p\nmid a_n$，則模 $p$ 的 $n$ 次同餘式$$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots a_1x+a_0\equiv 0\; (\textrm{mod}\; p)$$最多有 $n$ 個解。

<pf> 反證法。假設 $n$ 次同餘式 $$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots a_1x+a_0\equiv 0\; (\textrm{mod}\; p)$$ 的解超過 $n$ 個。其中 $a_n\not\equiv 0\; (\textrm{mod}\; p)$，則此式至少有 $n+1$ 個不同的解，設為 $$x\equiv \alpha _i\; (\textrm{mod}\; p)\; \; i=1,2,\cdots ,n,n+1.$$ 我們可以將原式改寫為$$f(x)\equiv a_n(x-\alpha _1)(x-\alpha _2)\cdots (x-\alpha _n)\; (\textrm{mod}\; p).$$因為$f(\alpha _{n+1})\equiv 0 (\textrm{mod}\; p)$，所以 $$a_n(\alpha _{n+1}-\alpha _1)(\alpha _{n+1}-\alpha _2)\cdots (\alpha _{n+1}-\alpha _n)\equiv 0\; (\textrm{mod}\; p).$$由於 $p$ 是質數，且 $a_n\not\equiv 0\; (\textrm{mod}\; p)$，故存在某個 $\alpha _i$，使得$$\alpha _{n+1}-\alpha _i\equiv 0\; (\textrm{mod}\; p)$$即$$\alpha _{n+1}\equiv \alpha _i\; (\textrm{mod}\; p)$$這與假設矛盾。所以此方程式最多只有 $n$ 個解。

Lagrange定理僅給了一個模 $p$ 的 $n$ 次同餘式解的個數上限，並不保證解的存在性。首先，我們想知道，在什麼情況下，解的個數恰好為 $n$ 個？


三、再探解的個數
性質一：設 $p$ 為質數。若 $n\leq p$，則同餘式$$f(x)=x^n+a_{n-1}x^{n-1}+\cdots a_1x+a_0\equiv 0\; (\textrm{mod}\; p)$$有 $n$ 個解的充分必要條件是 $x^p-x$ 除以 $f(x)$ 的餘式的所有係數都是 $p$ 的倍數。

<pf> 我們可以將 $x^p-x$ 寫為$$x^p-x=f(x)\cdot q(x)+r(x)$$其中 $q(x)$ 是一個 $p-n$ 次的多項式，餘式 $r(x)$ 的次數小於 $n$。

充分性$(\Rightarrow )$：若所給同餘式有 $n$ 個解，由上述 2.3 知，這 $n$ 個解也會是 $r(x)\equiv 0\; (\textrm{mod}\; p)$ 的解。但 $r(x)$ 的次數小於 $n$，根據 Lagrange 定理，$r(x)$ 的係數必定都是 $p$ 的倍數。

必要性$(\Leftarrow )$：若 $r(x)$ 的係數皆可被 $p$ 整除，因為 $x^p-x\equiv 0\; (\textrm{mod}\; p)$，所以有 $f(x)q(x)\equiv 0\; (\textrm{mod}\; p)$，有 $p$ 個不同的解$$x\equiv 0,1,\cdots ,p-1\; (\textrm{mod}\; p)$$若 $f(x)\equiv 0\; (\textrm{mod}\; p)$ 的解的個數 $k<n$，因為 $q(x)$ 是一個 $p-n$ 次的多項式，由 Lagrange 定理知，$q(x)\equiv 0\; (\textrm{mod}\; p)$ 的解的個數 $h\leq p-n$。因此 $f(x)q(x)\equiv 0\; (\textrm{mod}\; p)$ 的解的個數等於 $k+h<n+(p-n)=p$，但前面又說明此同餘式有 $p$ 個不同的解，故所給同餘式有 $n$ 個解。


性質二：設 $p$ 為質數，$d\mid p$，則同餘式 $x^d\equiv 1\; (\textrm{mod}\; p)$ 恰有 $d$ 個解。