这里我们先讨论一般情况 (但一点也不简单, 有很多厉害的定理), 二次剩余之后再说.
1. 一元同余方程的具体解法
我们考虑一般的一元同余方程 \(f(x)\equiv0\pmod m\), 容易想到将 \(m\) 素因数分解, 分别求解再进行合并. 这就需要下面的定理:
- 设 \(m=m_1\cdots m_k\) 且 \(m_j\) 两两互素. 则原方程等价于同余方程组 \(f(x)\equiv0\pmod {m_j}, 1\leqslant j\leqslant k\). 并且对于解数, 有 \(T(m;f)=T(m_1;f)\cdots T(m_k;f)\).
根据 5.1.9 易知等价性. 对于解数, 若存在 \(T(m_j;f)=0\) 显然成立.
根据中国剩余定理, \(k\) 个同余方程构成的方程组的解对应了原方程的一个解; 另一方面, 对原方程的解进行取模也能对应到方程组的解. 因此方程组的解和方程的解是一一对应的, 排列组合即得原式.
因此我们对 \(m\) 进行素因数分解 \(m=p_1^{\alpha_1}\cdots p_s^{\alpha_s}\), 令 \(m_j=p_j^{\alpha_j}\), 我们就将问题转化到了模为素数幂的情况. 下面我们给出具体求解方法.
- 设 \(f(x)=\sum\limits_{k=0}^na_kx^k,n\geqslant2\). 设 \(c\) 是 \(f(x)\equiv0\pmod{p^{\alpha-1}}\) 的解 \((\alpha\geqslant2)\), 则 \(f(x)\equiv0\pmod{p^\alpha}\) 满足 \(x\equiv c\pmod{p^{\alpha-1}}\) 的解为 \(x\equiv c+p^{\alpha-1}y_j\pmod{p^\alpha},1\leqslant j\leqslant l\), 其中 \(y\equiv y_j\pmod p\) 是 \(f'(c)y\equiv-f(c)p^{1-\alpha}\pmod p\) 的全部解, \(f'(x)\) 为 \(f(x)\) 的导函数.
根据 6.1.5, 实际上我们需要做的只有确定 \(x\equiv c+p^{\alpha-1}y_j\pmod{p^\alpha},1\leqslant j\leqslant l\) 中 \(y_j\) 满足的条件.
直接将 \(x=c+p^{\alpha-1}y\) 代入原方程:
中间使用二项式定理化简, 并消去了 \(p\) 的次数过高的项.
因为 \(c\) 是 \(f(x)\equiv0\pmod{p^{\alpha-1}}\) 的解, 有 \(p^{\alpha-1}|f(c)\), 由 5.1.6 化简即有
这就证明了原定理. 下面我们利用 6.1.6 对这个方程进行进一步的讨论:
- \((p,f'(c))=1\), 即 \(p\nmid f'(c)\): 容易发现有唯一解.
- \(p|f'(c),p\nmid f(c)p^{1-\alpha}\): 无解.
- \(p|f'(c),p|f(c)p^{1-\alpha}\): 解数为 \(p\), \(y\equiv0,\cdots,p-1\pmod p\).
上面的做法在实际计算时可能是非常麻烦的 (上述讨论的第三种情况会使解数增长迅速). 不过在特殊情况下, 也会是十分简单的:
- 设 \(c\) 是 \(f(x)\equiv0\pmod{p}\) 的解, 且 \(p\nmid f'(c)\), 则 \(f(x)\equiv0\pmod{p^\alpha}\) 满足 \(x\equiv c\pmod{p^{\alpha-1}}\) 的解数在 \(\alpha\geqslant2\) 时均为 \(1\).
根据上面讨论的第一种情况易得.
实例计算见习题篇.
2. 模为素数的一元高次同余方程
我们发现, 上面的解法中降低了素数的幂次, 归于模为素数的情况. 不过对于该情况我们还没有除了枚举以外的通用解法. 这里我们只进行初步讨论.
考虑同余方程 \(f(x)=\sum\limits_{j=0}^na_jx^j\equiv0\pmod p\), \(p\nmid a_n\). 设它有 \(k\) 个解 \(x\equiv c_1,\cdots,c_k\pmod p\). 我们有下面有力的定理:
- 存在唯一的一组正整数 \(\alpha_1,\cdots,\alpha_k\) 和整系数多项式 \(h_k(x),s_k(x)\), 使 \(f(x)=(x-c_1)^{\alpha_1}\cdots(x-c_k)^{\alpha_k}h_k(x)+ps_k(x)\), 其中 \(\deg s_k(x)<\alpha_1+\cdots+\alpha_k\leqslant n\), \(\deg h_k(x)=n-(\alpha_1+\cdots+\alpha_k)\geqslant0\), \(h_k(x)\) 的首项系数为 \(a_n\) 且满足 \(p\nmid h_k(c_j),1\leqslant j\leqslant k\).
定理的形式比较复杂, 考虑数学归纳法.
- \(k=1\):
易知 \(n\geqslant1\). 若 \(n=0\), 则必有 \(a_0\equiv0\pmod p\), 与 \(p\nmid a_n\) 矛盾.
设 \(f(x)=(x-c_1)h_{11}(x)+r_{11}\). 显然 \(h_{11}(x)\) 是 \(n-1\) 次多项式, 且首项系数为 \(a_n\). \(r_{11}\) 是常数.
代入 \(x=c_1\), 由 \(f(c_1)\equiv0\pmod{p}\) 知 \(p|r_{11}\), 则 \(r_{11}=ps_{11}\).
若 \(p|h_{11}(c_1)\), 同上有 \(h_{11}(x)=(x-c_1)h_{12}(x)+pr_{12}\), \(h_{12}(x)\) 是 \(n-2\) 次多项式, 且首项系数为 \(a_n\).
代入到上一式有 \(f(x)=(x-c_1)^2h_{12}(x)+ps_{12}(x)\), 其中 \(s_{12}(x)=(x-c_1)r_{12}+s_{11}\).
重复直到 \(p\nmid h_{1\alpha_1}(c_1)\), 此时有 \(f(x)=(x-c_1)^{\alpha_1}h_{1\alpha_1}(x)+ps_{1\alpha_1}(x)\) (简单数学归纳即可证明).
令 \(h_1(x)=h_{1\alpha_1}(x),s_1(x)=s_{1\alpha_1}(x)\) 即满足各项限制, 并且由构造过程知唯一性. - 假设已证明 \(k=l\) 成立, 要证 \(k=l+1\) 成立:
设 \(f(x)=(x-c_1)^{\alpha_1}\cdots(x-c_l)^{\alpha_l}h_l(x)+ps_l(x)\) 满足以上限制. 代入 \(x=c_{l+1}\), 由 \(f(c_{l+1})\equiv0\pmod p\) 易知 \(p|h_l(x)\). 又有 \(p\nmid a_n\), \(h_l(x)\) 的首项系数为 \(a_n\), 则 \(\deg h_l\geqslant1\).
根据 \(k=1\) 的情况, 易知 \(h_l(x)=(x-c_{l+1})^{\alpha_{l+1}}h_{l+1}(x)+pr_{l+1}(x)\) 满足限制条件.
代入即得 \(f(x)=(x-c_1)^{\alpha_1}\cdots(x-c_l)^{\alpha_l}(x-c_{l+1})^{\alpha_{l+1}}h_{l+1}(x)+p((x-c_1)^{\alpha_1}\cdots(x-c_l)^{\alpha_l}r_{l+1}(x)+s_l(x))\).
令 \(s_{l+1}(x)=(x-c_1)^{\alpha_1}\cdots(x-c_l)^{\alpha_l}r_{l+1}(x)+s_l(x)\), 容易验证各项限制和唯一性. 定理证毕.
如果在上面的定理中不限制 \(p\nmid h_k(c_j),1\leqslant j\leqslant k\), 我们有下面更弱的定理:
- 存在唯一的整系数多项式 \(g_k(x),r_k(x)\), 使 \(f(x)=(x-c_1)\cdots(x-c_k)g_k(x)+pr_k(x)\), 其中 \(\deg r_k(x)<k,\deg g_k(x)=n-k\geqslant 0\), 且 \(g_k(x)\) 的首项系数为 \(a_n\).
存在性根据上面的定理是显然的 (将次数高的 \((x-c_j)\) 项乘到 \(h_k(x)\) 里面即可). 只需证唯一性.
设还有 \(\bar{g}_k(x),\bar{r}_k(x)\) 满足条件. 则化简易得
右边的多项式次数更小, 因此只能有 \(\bar{g}_k(x)=g_k(x)\), \(\bar{r}_k(x)=r_k(x)\).
- \(T(p;f)\leqslant\min(n,p)\) (拉格朗日定理)
显然无解时成立, 且 \(T(p;f)\leqslant p\).
根据上面的定理 2 中 \(\deg g_k(x)=n-k\geqslant0\) 即有 \(T(p;f)\leqslant n\). 证毕.
根据上面的定理, 我们有简单的推论:
- 若 \(T(p;f)>n\), 则有 \(f(x)≣0\pmod p\).
- 若 \(\deg f_1(x)<p, \deg f_2(x)<p\), 则 \(f_1(x)\equiv f_2(x)\pmod p\Lrarr f_1(x)≣f_2(x)\pmod p\).
- \(T(p;f)=n\Lrarr f(x)=a_n(x-c_1)\cdots(x-c_n)+pr(x)\), 其中 \(c_j\) 两两模 \(p\) 不同余, \(\deg r(x)<n\).
必须注意的是, 这些结论能够成立的一个重要前提是, \(p\nmid a_n\).
我们发现上面的 6 给出了 \(T(p;f)=n\) 的一个充分必要条件. 实际上我们还有其它的结论.
- 若 \(a_n=1\), 则 \(T(p;f)=n\) 的充分必要条件为 \(x^p-x=f(x)q(x)+pr(x)\), \(q(x),r(x)\) 都是整系数多项式, \(\deg r(x)<n\).
- 必要性:
解数为 \(n\), 故 \(n\leqslant p\). 直接做多项式除法.
3. 多元同余方程
(多元同余方程中的概念可以类比一元同余方程, 这里不列举了)
一般来说解多元同余方程是很困难的. 不过我们还是能得出一些有用的结果.