同餘方程
定義
同餘方程
對正整數 \(m\) 和一元整係數多項式 \(f(x)=\sum_{i=0}^n a_ix^i\)，其中未知數 \(x\in\mathbf{Z}_m\)，稱形如
的方程為關於未知數 \(x\) 的模 \(m\) 的一元 同餘方程（Congruence Equation）。
若 \(a_n\not\equiv 0\pmod m\)，則稱上式為 \(n\) 次同餘方程。
類似可定義同餘方程組。
關於一次同餘方程與方程組的相關內容請參見 線性同餘方程 與 中國剩餘定理。
本文首先研究同餘方程的可解性和解集結構，之後會簡要介紹高次同餘方程的解法。
由 中國剩餘定理 可知，求解關於模合數 \(m\) 的同餘方程可轉化為求解模素數冪次的情況。故以下只介紹素數冪模同餘方程和素數模同餘方程的相關理論。
素數冪模同餘方程
以下假設模數 \(m=p^a~(p\in\mathbf{P},a\in\mathbf{Z}_{>1})\).
注意到若 \(x_0\) 是方程
的解，則 \(x_0\) 是方程
的解，這啓發我們嘗試通過較低的模冪次的解去構造較高的模冪次的解。我們有如下定理：
定理 1
對素數 \(p\) 和整數 \(a>1\)，取整係數多項式 \(f(x)=\sum_{i=0}^na_ix^i~(p^a\nmid a_n)\)，令 \(f'(x)=\sum_{i=1}^nia_ix^{i-1}\) 為其導數。令 \(x_0\) 為方程
的解，則：
-
若 \(f'(x_0)\not\equiv 0\pmod p\), 則存在整數 \(t\) 使得
\[ x=x_0+p^{a-1}t\tag{3} \]是方程
\[ f(x)\equiv 0\pmod{p^a}\tag{4} \]的解。
-
若 \(f'(x_0)\equiv 0\pmod p\) 且 \(f(x_0)\equiv 0\pmod{p^a}\), 則對 \(t=0,1,\dots,p-1\)，由式 \((3)\) 確定的 \(x\) 均為方程 \((4)\) 的解。
-
若 \(f'(x_0)\equiv 0\pmod p\) 且 \(f(x_0)\not\equiv 0\pmod{p^a}\), 則不能由式 \((3)\) 構造方程 \((4)\) 的解。
證明
我們假設式 \((3)\) 是方程 \((4)\) 的解，即
整理後可得
於是
- 若 \(f'(x_0)\not\equiv 0\pmod p\)，則關於 \(t\) 的方程 \((5)\) 有唯一解 \(t_0\)，代入式 \((3)\) 可驗證其為方程 \((4)\) 的解。
- 若 \(f'(x_0)\equiv 0\pmod p\) 且 \(f(x_0)\equiv 0\pmod{p^a}\)，則任意 \(t\) 均能使方程 \((5)\) 成立，代入式 \((3)\) 可驗證其均為方程 \((4)\) 的解。
- 若 \(f'(x_0)\equiv 0\pmod p\) 且 \(f(x_0)\not\equiv 0\pmod{p^a}\)，則方程 \((5)\) 無解，從而不能由式 \((3)\) 構造方程 \((4)\) 的解。
進而我們有推論：
推論 1
對 定理 1 的 \(p\)，\(a\)，\(f(x)\)，\(x_0\)，
- 若 \(s\) 是方程 \(f(x)\equiv 0\pmod p\) 的解，且 \(f'(a)\not\equiv 0\pmod p\)，則存在 \(x_s\in\mathbf{Z}_{p^a}\)，\(x_s\equiv s\pmod p\) 使得 \(x_s\) 是方程 \((4)\) 的解。
- 若方程 \(f(x)\equiv 0\pmod p\) 與 \(f'(a)\equiv 0\pmod p\) 無公共解，則方程 \((4)\) 和方程 \(f(x)\equiv 0\pmod p\) 的解數相同。
從而我們可以將素數冪模同餘方程化歸到素數模同餘方程的情況。
素數模同餘方程
以下令 \(p\in\mathbf{P}\)，整係數多項式 \(f(x)=\sum_{i=0}^na_ix^i\)，其中 \(p\nmid a_n\)，\(x\in\mathbf{Z}_p\).
定理 2
若方程
有 \(k\) 個不同的解 \(x_1,x_2,\dots,x_k~(k\leq n)\)，則：
其中 \(\deg g=n-k\) 且 \([x^{n-k}]g(x)=a_n\).
證明
對 \(k\) 應用數學歸納法。
-
當 \(k=1\) 時，做多項式帶餘除法，有 \(f(x)=(x-x_1)g(x)+r\)，其中 \(r\in\mathbf{Z}\).
由 \(f(x_1)\equiv 0\pmod p\) 可知 \(r\equiv 0\pmod p\)，從而 \(f(x)\equiv(x-x_1)g(x)\pmod p\).
-
假設命題對 \(k-1\)(\(k>1\)) 時的情況成立，現在設 \(f(x)\) 有 \(k\) 個不同的解 \(x_1,x_2,\dots,x_k\), 則 \(f(x)\equiv(x-x_1)h(x)\pmod p\), 進而有
\[ (\forall i=2,3,\dots,k),~~0\equiv f(x_i)\equiv (x_i-x_1)h(x_i)\pmod p \]從而 \(h(x)\) 有 \(k-1\) 個不同的解 \(x_2,x_3,\dots,x_k\), 由歸納假設有
\[ h(x)\equiv g(x)\prod_{i=2}^k(x-x_i)\pmod p \]其中 \(\deg g=n-k\) 且 \([x^{n-k}]g(x)=a_n\).
因此命題得證。
推論 2
對素數 \(p\)，
- \((\forall x\in\mathbf{Z}),~~x^{p-1}-1 \equiv \prod_{i=1}^{p-1}(x-i)\pmod p\)
- （Wilson 定理）\((p-1)! \equiv -1 \pmod p\)
定理 3（Lagrange 定理）
方程 \((6)\) 至多有 \(n\) 個不同解。
證明
假設 \(f(x)\) 有 \(n+1\) 個不同解 \(x_1,x_2,\dots,x_{n+1}\)，則由 定理 2，對 \(x_1,x_2,\dots,x_n\) 有
令 \(x=x_{n+1}\), 則
而右側顯然不是 \(p\) 的倍數，因此假設矛盾。
推論 3
若同餘方程 \(\sum_{i=0}^nb_ix^i\equiv 0\pmod p\) 的解數大於 \(n\)，則
定理 4
方程 \((6)\) 若解的個數不為 \(p\)，則必存在滿足 \(\deg r<p\) 的整係數多項式 \(r(x)\) 使得 \(f(x)\equiv 0\pmod p\) 和 \(r(x)\equiv 0\pmod p\) 的解集相同。
證明
不妨設 \(n\geq p\)，對 \(f(x)\) 做多項式帶餘除法
其中 \(\deg r<p\).
由 Fermat 小定理 知對任意整數 \(x\) 有 \(x^p\equiv x\pmod p\)，從而
- 若 \(r(x)\equiv 0\pmod p\)，則由 推論 2 可知 \(f(x)\) 有 \(p\) 個不同的解。
- 若 \(r(x)\not\equiv 0\pmod p\)，則由 \(f(x)\equiv r(x)\pmod p\) 可知 \(f(x)\) 和 \(r(x)\) 的解集相同。
我們可以通過這個定理對同餘方程降次。
定理 5
設 \(n\leq p\)，則方程
有 \(n\) 個解當且僅當存在整係數多項式 \(q(x)\)，\(r(x)~(\deg r < n)\) 使得
證明
-
必要性：由多項式除法知存在整係數多項式 \(q(x)\)，\(r_1(x)~(\deg r_1 < n)\) 使得
\[ x^p-x=f(x)q(x)+r_1(x) \]若方程 \((7)\) 有 \(n\) 個解，則 \(r_1\equiv 0\pmod p\) 也有 \(n\) 個相同的解，進而由 推論 3 可知存在整係數多項式 \(r(x)\) 滿足 \(r_1(x)=pr(x)\)，從而命題得證。
-
充分性：若式 \((8)\) 成立，則由 Fermat 小定理 可知，對任意整數 \(x\),
\[ 0\equiv x^p-x\equiv f(x)q(x)\pmod p \]即方程 \(f(x)q(x)\equiv 0\pmod p\) 有 \(p\) 個解。
設方程 \((7)\) 的解數為 \(s\)，則由 Lagrange 定理 可知 \(s\leq n\).
又由於 \(\deg q=p-n\)，則由 Lagrange 定理 可知 \(q(x)\equiv 0\pmod p\) 的解數不超過 \(p-n\)，而方程 \(f(x)q(x)\equiv 0\pmod p\) 的解集是 \(f(x)\equiv 0\pmod p\) 解集和 \(q(x)\equiv 0\pmod p\) 解集的並集，故 \(s+(p-n)\geq p\)，有 \(s\geq n\).
因此 \(s=n\).
對於非首 1 多項式，由於 \(\mathbf{Z}_p\) 是域，故可以將其化為首 1 多項式，從而適用該定理。
定理 6
設 \(n\nmid p-1\)，\(p\nmid a\), 則方程
有解當且僅當
且若 \((9)\) 有解，則解數為 \(n\).
Note
方程 \((9)\) 解集的具體結構可參見 k 次剩餘。
證明
-
必要性：若方程 \((9)\) 有解 \(x_0\)，則
\[ a^{\frac{p-1}{n}}\equiv {\left(x_0^n\right)}^{\frac{p-1}{n}}\equiv 1\pmod p \] -
充分性：若 \(a^{\frac{p-1}{n}}\equiv 1\pmod p\)，則
\[ \begin{aligned} x^p-x&=x\left(x^{p-1}-1\right)\\ &=x\left(\left(x^n\right)^{\frac{p-1}{n}}-a^{\frac{p-1}{n}}+a^{\frac{p-1}{n}}-1\right)\\ &=\left(x^n-a\right)P(x)+x\left(a^{\frac{p-1}{n}}-1\right)\\ \end{aligned} \]其中 \(P(x)\) 是某個整係數多項式，因此由 定理 5 可知方程 \((9)\) 有 \(n\) 個解。
高次同餘方程（組）的求解方法
首先我們可以藉助 中國剩餘定理 將求解 同餘方程組 轉為求解 同餘方程，以及將求解模 合數 \(m\) 的同餘方程轉化為求解模 素數冪次 的同餘方程。之後我們藉助 定理 1 將求解模 素數冪次 的同餘方程轉化為求解模 素數 的同餘方程。
結合模素數同餘方程的若干定理，我們只需考慮方程
的求法，其中 \(p\) 是素數，\(n<p\).
我們可以通過將 \(x\) 代換為 \(x-\dfrac{a_{n-1}}{n}\) 來消去 \(x^{n-1}\) 項，從而我們只需考慮方程
的求法，其中 \(p\) 是素數，\(n<p\).
- 若 \(n=1\)，則求法參見 線性同餘方程。
- 若 \(n=2\)，則求法參見 二次剩餘。
-
若方程 \((10)\) 可化為
\[ x^n\equiv a\pmod p \]則求法參見 k 次剩餘。
參考資料
- Congruence Equation -- from Wolfram MathWorld
- Lagrange's theorem (number theory) - Wikipedia
- 潘承洞，潘承彪。初等數論。
- 馮克勤。初等數論及其應用。
- 閔嗣鶴，嚴士健。初等數論。
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：iamtwz, aofall, CCXXXI, CoelacanthusHex, Great-designer, Marcythm, Persdre, shuzhouliu, Tiphereth-A, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用