同余方程

对正整数 $m$ 和一元整系数多项式 $f(x)={\sum }_{i=0}^n{a}_i{x}^i$，其中未知数 $x\in {\mathbf{Z}}_m$，称形如

$$f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}m)$$

的方程为关于未知数 $x$ 的模 $m$ 的一元 同余方程（Congruence Equation）.

若 $a_n\not\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}m)$，则称上式为 $n$ 次同余方程.

类似可定义 同余方程组.

线性同余方程

若 $d=(a,m)$，则线性同余方程

$$ax\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$$

有解当且仅当 $d\mid b$.

若 $d\mid b$，且 $x_0$ 为任意解，则通解为

$$x=x_0+\frac{nt}{d},t\in \mathbf{Z}$$

特别地，这个解集正好生成了 $d$ 个模 $m$ 同余类，有

$$x=x_0,x_0+\frac{m}{d},x_0+\frac{2m}{d},\dots ,x_0+\frac{(d-1)m}{d}$$

求解方法为求解 线性丢番图方程 $ax+km=b$.

线性同余方程组求解参见 中国剩余定理.

高次同余方程

$$f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}m)$$

使用原根求解 $x^n\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}m)$

1. 找到模 $m$ 的原根。
2. 将方程转化为指数形式。
3. 求解对应的离散对数问题。
4. 使用同余方程求解方法得到最终解。

例如 $x^3\equiv 2(\mathrm{m}\mathrm{o}\mathrm{d}11)$.

$2$ 是 $11$ 的一个原根. 设 $x=2^k(\mathrm{m}\mathrm{o}\mathrm{d}11)$.

$$2^{3k}\equiv 2(\mathrm{m}\mathrm{o}\mathrm{d}11)$$

由费马小定理，$2^{10}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}11)$，所以

$$\begin{gathered} 3k\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}10) \\ k\equiv 7(\mathrm{m}\mathrm{o}\mathrm{d}10) \end{gathered}$$

所以 $x\equiv 2^7(\mathrm{m}\mathrm{o}\mathrm{d}11)$.

模数分解

假设我们有一个高次同余方程，如：

$$x^n\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}m)$$

其中 $m$ 可以因式分解为多个质因数，例如 $m=p_1^{e_1}\cdot p_2^{e_2}\cdot \cdots \cdot p_k^{e_k}$，则可以将方程拆解为一组关于每个质因数的同余方程。

模数提升

由方程 $f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p)$ 的解进一步得到 $f(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}^k)$.

详见 亨泽尔引理.

参考

https://oi-wiki.org/math/number-theory/congruence-equation/