同余式
定义
$m \in Z^+$，$f(x)=a_nx^n+ \cdots + a_0$，且 $a_i \in Z$，则
$$
f(x) \equiv 0 \quad (mod \; m)
$$
称为模 $m$ 同余式，若 $a_n \neq 0 \quad (mod \; m)$，则 $n$ 叫做 $f(x)$ 的次数，记为 $deg f$，上述式子还可以称为模 $m$ 的 $n$ 次同余式，若 $x \equiv a \quad (mod \; m)$ 使得上述式子成立，则称其为同余式的解
一次同余式
$m \in Z^+$，$a \in Z$ 且 $m \nmid a$，则一次同余式
$$
ax \equiv b \quad (mod \; m)
$$
有解的充要条件是 $(a, m) | b$，若有解，则其解为：
$$
x \equiv \cfrac{b}{(a, m)}((\cfrac{a}{(a, m)})^{-1} \quad (mod \; \cfrac{m}{(a, m)})) + t \cdot \cfrac{m}{(a, m)} \quad (mod \; m)
$$
例子：求解同余式
$$
33x \equiv 22 \quad (mod \; 77)
$$
$(33, 77) = 11 | 22 \implies$ 有解
$3x \equiv 2 \quad (mod \; 7)$ 的解为3
故全部解为 $3 + 7t, \quad t \in [0, 10]$
中国剩余定理
设 $m_i$ 是 $k$ 个两两互素的正整数，则 $\forall b_i$，同余式组
$$
\begin{cases}
x \equiv b_1 \quad (mod \; m_1) \\
\dots \\
x \equiv b_k \quad (mod \; m_k)
\end{cases}
$$
有唯一解，若零 $m = \Pi m_i$，$m = m_i \cdot M_i$，$M_i^{-1}M_i \equiv 1 \quad (mod \; m_i)$，则
$$
x \equiv \sum b_i \cdot M_i \cdot M_i^{-1} \quad (mod \; m)
$$
例子：求解同余式组
$$
\begin{cases}
x \equiv b_1 \quad (mod \; 5) \\
x \equiv b_2 \quad (mod \; 6) \\
x \equiv b_3 \quad (mod \; 7) \\
x \equiv b_4 \quad (mod \; 11)
\end{cases}
$$
$M_1=6 \times 7 \times 11 = 462$，类似求得 $M_2=385$，$M_3=330$，$M_4=210$
$3 \times M_1 \equiv 1 \quad (mod \;5) \implies M_1^{-1}=3$，类似球的 $M_2^{-1}=1$，$M_3^{-1}=1$，$M_4^{-1}=1$
带入可知解为
$$
x \equiv 1386b_1 + 385b_2 + 330b_3 + 210b_4 \quad (mod \; 2310)
$$
高次同余式的解数及解法
中国剩余定理+暴力计算
略
高次同余式的提升
当 $p$ 为素数时，求解多项式 $f(x) \equiv 0 \quad (mod \; p^{\alpha})$
设 $x \equiv x_1 \quad (mod \; p)$ 是同余式
$$
f(x) \equiv 0 \quad (mod \; p)
$$
的一个解，且
$$
(f’(x_1), p) = 1
$$
则 $f(x) \equiv 0 \quad (mod \; p^{\alpha})$ 有解
$$
x \equiv x_{\alpha} \quad (mod \; p^{\alpha})
$$
其中 $x_{\alpha}$ 满足递归关系式
$$
\begin{align}
& x_i \equiv x_{i-1} + t_{i-1} \cdot p^{i-1} \quad (mod \; p^i) \\
& t_{i-1} \equiv \cfrac{-f(x_{i-1})}{p^{i-1}} \cdot (f’(x_1)^{-1} \; (mod \; p)) \quad (mod \; p)
\end{align}
$$
例子：求解同余式 $f(x) \equiv x^4 + 7x + 4 \equiv 0 \quad (mod \; 27)$
易得 $f(x) \equiv 0 \quad (mod \; 3)$ 的解为 $x_1 \equiv 1$，又 $f’(x_1) = 11 \implies (11, 3) = 1$ 故有解，且 $f’(x_1)^{-1} \equiv 2 \quad (mod \; 3)$ 根据递推关系式可计算得到 $t_1 \equiv 2, x_2 \equiv 4, t_2 \equiv 2, x_3 \equiv 22 $ ，故解为22
求解素数模的同余式
多项式欧几里得除法
$f(x)$ 为 $n$ 次整系数多项式，$g(x)$ 为 $m$ 次首一整系数多项式，则存在整系数多项式 $q(x)$ 和 $r(x)$，使得
$$
f(x) = q(x) \cdot g(x) + r(x), \qquad deg \; r(x) < deg \; g(x)
$$
由费马小定理及上述结论可知 $f(x)$ 与一个次数不超过 $p-1$ 的模 $p$ 同余式等价
$$
f(x) = q(x) \cdot (x^p - x) + r(x)
$$
素数模同余式的因式分解
素数模同余式满足因式分解定理
素数模同余式的解数估计
$f(x)$ 的解数不超过其次数(因式分解立证)
解的判断
$p$ 是一个素数，$n \in Z^+$，$n \le p$，则
$$
f(x) = x^n + \cdots + a_1x + a_0 \equiv \quad (mod \; p)
$$
有 $n$ 个解的充要条件是 $x^p - x$ 被 $f(x)$ 除所得的余式的所有系数都是 $p$ 的倍数
例子：判断同余式
$$
2x^3 + 5x^2 + 6x + 1 \equiv 0 \quad (mod \; 7)
$$
是否有三个解
首先将多项式两边 $\times 4$ 变成首1多项式
$$
4 \times (2x^3 + 5x^2 + 6x + 1) \equiv x^3 - x^2 + 3x - 3
$$
又有
$$
x^7 - x \equiv x(x^3+x^2-2x-2) \cdot (x^3 - x^2 + 3x - 3) + 7x(x^2-1)
$$
故有三个解
