期末月不想看模电，花了两天搞这个东西……我有病吧……
参考资料：潘承洞，潘承彪．初等数论．3 版．
本节要讨论的是一元同余方程
的一般求解算法．
定理 1 设 \(m=m_1\cdots m_k\)，其中 \(m_1,\cdots,m_k\) 两两既约，则同余方程 \((1)\) 与同余方程组
\[f(x)\equiv0\pmod{m_j},\quad j=1,\cdots,k\tag2 \]的解和解数相同，且 \((1)\) 的解数等于 \((2)\) 中每个方程的解数的乘积．
证明 首先，由同余式的性质知 \((1)\) 和 \((2)\) 的解相同．对于 \((1)\) 的每个解 \(x\equiv a\pmod m\)，在 \((2)\) 中的 \(k\) 个方程中都能找到唯一的一组 \(a_1,\cdots,a_k\) 满足 \(a\equiv a_j\pmod{m_j}\)．而对于给定的 \(a_1,\cdots,a_j\)，由中国剩余定理知方程组 \(x\equiv a_j\pmod{m_j}\) 有唯一解 \(x\equiv c\pmod m\)，显然 \(c\) 是 \((1)\) 的解．这样就在 \((1)\) 的每一个解和 \((2)\) 中所有方程的所有解的每一个组合之间建立起了一一对应关系，故 \((1)\) 的解数等于 \((2)\) 中每个方程解数的乘积．证毕．
由定理 1 可以得到求解 \((1)\) 的方法，即把 \(m\) 进行素因数分解，然后求每一个 \(f(x)\equiv0\pmod{m_j}\) 的所有解，再对这 \(k\) 列解的所有组合 \(a_1,\cdots,a_k\) 求方程组 \(x\equiv a_j\pmod{a_j}\) 的解，得到一个解 \(x\equiv a\pmod m\)．
下面讨论如何求 \(m=p^\alpha\) 时 \((1)\) 的解．先引入一个定理．
定理 2 若同余方程 \((1)\) 有解，则对任一约数 \(d\mid m\)，同余方程
\[f(x)\equiv0\pmod d\tag3 \]也有解，且 \((1)\) 的每个解 \(a\) 与 \((3)\) 的每个解 \(c\) 一一对应，其中满足 \(a\equiv c\pmod d\)．
证明是容易的．进一步地，设由 \((3)\) 得到的解为 \(c_1,\cdots,c_s\)，那么对每一个 \(c_i\) 解同余方程
即可得到同余方程 \((1)\) 的解 \(x=c_i+dy\)．
这样，对于 \(m=p^\alpha\) 的情形，就可以从 \(m=p,p^2,\cdots\) 的情形上来一步步求解得到，而每一步都只需要解一次同余方程（下面将证明这一点）．
定理 3 设 \(p\) 是素数，整系数多项式
\[f(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_1x+a_0,\quad n\ge2, \]再设整数 \(\alpha\ge2\)，\(c\) 是同余方程
\[f(x)\equiv0\pmod{p^{\alpha-1}}\tag5 \]的解．那么，同余方程
\[f(x)\equiv0\pmod{p^\alpha}\tag6 \]满足
\[x\equiv c\pmod{p^{\alpha-1}}\tag{6.5} \]的解是
\[x\equiv c+y_jp^{\alpha-1}\pmod{p^\alpha},\quad j=1,\cdots,l,\tag7 \]其中 \(y\equiv y_1,\cdots,y_l\pmod p\) 是一次同余方程
\[f'(c)y\equiv-f(c)p^{1-\alpha}\pmod p\tag8 \]的全部解，其中 \(f'\) 为 \(f\) 的导函数．
证明 设 \((6)\) 的满足条件的解形式为 \(x=c+yp^{\alpha-1}\)，根据多项式的 Taylor 展开
其中 \(\dfrac{f^{(i)}(c)}{i!}\)（\(i=1,\cdots,n\)）为整数，令 \(x=c+yp^{\alpha-1}\) 得
其中 \(A_2,\cdots,A_n\) 为整数．由 \(\alpha\ge2\) 知 \(k(\alpha-1)\ge\alpha\)（\(k=2,\cdots,n\)），故右侧第三项开始后面都为零，上式即
由于 \(c\) 是方程 \((5)\) 的解，故 \(p^{\alpha-1}\mid f(c)\)，进而由同余式的除法性质 \(ac\equiv bc\pmod m\iff a\equiv b\pmod{m/(c,m)}\)，得到式 \((8)\)．这说明，相应于一次同余方程 \((8)\) 的全部解 \(y_1,\cdots,y_l\)，式 \((7)\) 给出了同余方程组 \((5)(6)\) 的全部的解；反过来，同时满足 \((5)(6)\) 的解 \(x\) 一定能表为式 \((7)\) 的形式，其中 \(y_j\) 为一次同余方程 \((8)\) 的解．这样就证明了这种一一对应关系．证毕．
根据定理 3，可以得到求解模数为 \(p^\alpha\) 的同余方程的一般算法．由 \(p\) 为素数，可以进一步讨论，有下面三种情形：
- \(p\nmid f'(c)\)．此时同余方程 \((8)\) 的解数为 \(1\)．
- \(p\mid f'(c)\)，\(p\nmid f(c)p^{1-\alpha}\)，即 \(p^\alpha\nmid f(c)\)．此时同余方程 \((8)\) 无解．
- \(p\mid f'(c)\)，\(p\mid f(c)p^{1-\alpha}\)，即 \(p^\alpha\mid f(c)\)．此时同余方程 \((8)\) 恒成立，即有 \(p\) 个解
由此可得到一个有用的结论：
推论 4 在定理 3 的符号和条件下，设 \(c\) 是方程 \(f(x)\equiv0\pmod p\) 的解．若 \(p\nmid f'(c)\)，则对任意 \(\alpha\ge2\)，同余方程
\[f(x)\equiv0\pmod{p^\alpha}\tag6 \]满足式 \((6.5)\) 的解数均为 \(1\)，且这个解 \(c_\alpha\) 满足 \(c_\alpha\equiv c\pmod p\)．特别地，若 \(f(x)\equiv0\pmod p\) 与 \(f'(x)\equiv0\pmod p\) 无公共解，则同余方程 \((6)\) 对任意 \(\alpha\ge1\) 解数均相同．
证明 数学归纳法．设 \(c\) 是方程 \(f(x)\equiv0\pmod p\) 的解，且 \(p\nmid f'(c)\)．基础步骤：首先对于 \(\alpha=2\)，同余方程
的解数为 \(1\)，进而将这个唯一解 \(y\) 代入
得到 \((6)\)（\(\alpha=2\)）的唯一解 \(x=c_2\)，其满足 \(c_2\equiv c\pmod p\)．
归纳步骤：假设对某一 \(\alpha=k\ge2\)，方程 \((6)\)（\(\alpha=k\)）有唯一解 \(c_k\pmod{p^k}\) 满足 \(c_k\equiv c_{k-1}\pmod{p^{k-1}}\)（\(c_1=c\)），且 \(c_k\equiv c\pmod p\)．由同余式的性质知 \(f'(c_k)\equiv f'(c)\pmod p\)，从而 \(p\nmid f'(c_k)\)．那么 \(c_k\) 满足上面的情形 1．由此可以得到 \((8)\)（\(\alpha=k+1\)）的唯一解，进而得到 \((6)\)（\(\alpha=k+1\)）的唯一解 \(c_{k+1}\pmod{p^{k+1}}\) 满足 \(c_{k+1}\equiv c_k\pmod{p^k}\)．并且 \(c_{k+1}\equiv c_k\equiv c\pmod p\)．这样，假设对 \(\alpha=k+1\) 也成立，进而对任意 \(\alpha\ge2\) 都成立．
特别地，若 \(f(x)\equiv0\pmod p\) 与 \(f'(x)\equiv0\pmod p\) 无公共解，这等价于 \(f(x)\equiv0\pmod p\) 的每一个解 \(x_j\)（\(j=1,\cdots,s\)）都满足 \(p\nmid f'(x_j)\)，进而由前半部分的结论，对每一个解 \(x_j\)，\((6)\) 对任意 \(\alpha\ge2\) 都有一个满足 \((6.5)\) 的解．从而，对于 \(\alpha=1,2,\cdots\)，总的解数始终为 \(s\)．证毕．
根据证明过程也可以得到，\(f'(c)\equiv f'(c_k)\pmod p\)，\(k=1,2,\cdots\)．那么一旦确定了一开始的 \(c\)，则不管 \(\alpha\) 多大，都要么属于情况 1，要么属于情形 2 或 3．
下面举几个例子，来说明上述定理及推论的应用．
例 1 设 \(f(x)=x^3+5x^2+9\)，解同余方程 \(f(x)\equiv0\pmod{3^4}\)．
解 依次解模数为 \(3,3^2,3^3,3^4\) 的同余方程．\(f'(x)=3x^2+10x\)．枚举知同余方程 \(f(x)\equiv0\pmod3\) 有两个解 \(0,1\)．
-
先求相应于 \(x\equiv0\pmod3\) 的解．\(3\mid f'(0)=0\)，属于情形 2 和 3．
-
\(\alpha=2\)：\(f(0)=9\)，故 \(3^2=9\mid f(0)\)，属于情形 3，则 \(y\equiv-1,0,1\pmod3\)，再代入 \((7)\) 得 \(x\equiv-3,0,3\pmod{3^2}\)．
-
\(\alpha=3\)：\(f(-3)=27,f(0)=9,f(3)=54\)，其中只有 \(f(0)\) 不能整除 \(3^3\)，属于无解的情形 2．其余二者属于情形 3，则 \(y\equiv-1,0,1\pmod3\)，代入 \((7)\) 得，对应于 \(x\equiv-3,3\pmod{3^2}\) 的解分别为
\[x\equiv-12,-3,6,\quad-6,3,12\pmod{3^3}. \] -
\(\alpha=4\)：计算可知，\(f(-12),f(-3),f(-6),f(12)\) 不能整除 \(3^4\)，属于无解的情形 2．\(f(6),f(3)\) 能整除 \(3^4\)，将 \(y\equiv-1,0,1\pmod3\) 代入 \((7)\) 得，对应于 \(x\equiv6,3\pmod{3^3}\) 的解分别为
\[x\equiv-21,6,33,\quad-24,3,30\pmod{3^4}. \]
-
-
再求相应于 \(x\equiv1\pmod3\) 的解．由于 \(3\nmid f'(1)=13\)，属于情形 1．那么对于 \(\alpha=2,3,4\)，都只有唯一解．
- \(\alpha=2\)：\(f(1)=15\)，将 \(c=1\) 代入 \((8)\) 得 \(y\equiv1\pmod3\)，再代入 \((7)\) 得 \(x\equiv4\pmod{3^2}\)．
- \(\alpha=3\)：\(f(4)=153\)，将 \(c=4\) 代入 \((8)\) 得 \(y\equiv1\pmod3\)，再代入 \((7)\) 得 \(x\equiv13\pmod{3^3}\)．
- \(\alpha=4\)：\(f(13)=3051\)，将 \(c=13\) 代入 \((8)\) 得 \(y\equiv1\pmod3\)，再代入 \((7)\) 得 \(x\equiv40\pmod{3^4}\)．
综上，\(x\equiv-21,6,33,-24,3,30,40\pmod{3^4}\) 为原方程的解．下图展示了求解的过程．
例 2 设 \(f(x)=x^3+5x^2+9\)，解同余方程 \(f(x)\equiv0\pmod{7\cdot3^4}\)．
解 由定理 1 知，这就是要解同余方程组
直接枚举可知前者的解为 \(x\equiv-2\pmod7\)，由例 1 可知后者的解为 \(x\equiv-21,6,33,-24,3,30,40\pmod{3^4}\)．进而解一次同余方程组
其中 \(a_1=-2\)，\(a_2=-21,6,33,-24,3,30,40\)．由中国剩余定理知，设 \(m_1=M_2=7,m_2=M_1=3^4\)，则 \((3^4)^{-1}\equiv4^{-1}\equiv2\pmod7\)，\(7^{-1}\equiv-23\pmod{3^4}\)，故方程的解为
代入得原方程的全部 \(7\) 个解为
虽然定理 3 给出了模为素数幂的同余方程的一般解法，但有时是很麻烦的．多多观察题目的性质，往往能简化计算．
例 3 解同余方程 \(x^2+x+7\equiv0\pmod{3^3}\)．
解 方程等价于 \(4(x^2+x+7)\equiv0\pmod{3^3}\)，而左端等于 \((2x+1)^2+27\equiv(2x+1)^2\pmod{3^3}\)，这又等价于 \(2x+1\equiv0\pmod{3^2}\)，枚举得到 \(x\equiv4\pmod{3^2}\)．令 \(f(x)=x^2+x+7\)，由 \(3\mid f(4)=27\) 且 \(3\mid f(4)\cdot p^{1-3}=3\) 知，属于情形 III，故在 \((7)\) 中代入 \(c=4,y=-1,0,1\) 得 \(x\equiv-5,4,13\pmod{3^3}\)．
例 4 求同余方程 \((x+1)^7-x^7-1\equiv0\pmod{7^7}\) 满足条件 \(7\nmid x(1+x)\) 的解．
解 注意到 \(-1,0\) 为左边多项式的根．二项式展开并因式分解得
先在方程两边除以 \(7\) 得
由于所求的解要满足 \(7\nmid x(1+x)\)，两边再除以 \(x(x+1)\) 得
即
按照上面的求解方法，一步步求解得