二项同余方程
我们来探讨一个基础但核心的数论对象：二项同余方程。我们将从最简单的概念开始，逐步深入到其解的结构与性质。
第一步：基本定义与简化
二项同余方程，是指形如
\[ x^n \equiv a \pmod{m} \]
的方程，其中 \(m, n\) 是给定的正整数，\(a\) 是一个整数，我们要求解的是整数 \(x\)（通常考虑模 \(m\) 的剩余类）。
首先，我们可以利用中国剩余定理，将模数 \(m\) 进行分解。如果 \(m = m_1 m_2\)，且 \(\gcd(m_1, m_2)=1\)，则原方程等价于求解方程组：
\[ x^n \equiv a \pmod{m_1}, \quad x^n \equiv a \pmod{m_2} \]
因此，研究的关键通常归结到模数为素数幂 \(p^k\) 的情形。我们首先研究最基础、最重要的模素数 \(p\) 的情况。
第二步：模素数 \(p\) 的情形（n次剩余）
考虑方程 \(x^n \equiv a \pmod{p}\)，其中 \(p\) 为素数，\(p \nmid a\)（若 \(p \mid a\)，则解是显然的，即所有 \(p\) 的倍数的剩余类）。
- 存在性判定（欧拉准则的推广）：设 \(g\) 是模 \(p\) 的一个原根，则任何与 \(p\) 互素的 \(a\) 可以唯一表示为 \(a \equiv g^u \pmod{p}\)，其中 \(u\) 是模 \(\phi(p)=p-1\) 的指数（即离散对数）。设 \(x \equiv g^y \pmod{p}\)，则方程化为：
\[ g^{ny} \equiv g^u \pmod{p} \iff ny \equiv u \pmod{p-1} \]
这是一个关于 \(y\) 的一次同余方程。
2. 解的存在性定理：上述线性同余方程 \(ny \equiv u \pmod{p-1}\) 有解，当且仅当 \(d = \gcd(n, p-1)\) 整除 \(u\)。
因此，\(x^n \equiv a \pmod{p}\) 有解（此时称 \(a\) 是模 \(p\) 的 n 次剩余），当且仅当 \(d \mid u\)。利用原根表示，这等价于：
\[ a^{(p-1)/d} \equiv 1 \pmod{p} \]
特别地，当 \(n=2\) 时，这就是我们熟知的欧拉准则。
3. 解的个数：如果解存在，则线性同余方程 \(ny \equiv u \pmod{p-1}\) 模 \(p-1\) 恰好有 \(d\) 个解 \(y\)。由于 \(x = g^y\)，且 \(g\) 的阶是 \(p-1\)，不同的 \(y\) 模 \(p-1\) 对应不同的 \(x\) 模 \(p\)。因此，原方程模 \(p\) 恰好有 \(d\) 个不同的解。
第三步：模素数幂 \(p^k\) 的情形（亨泽尔引理的应用）
现在考虑 \(x^n \equiv a \pmod{p^k}\)，其中 \(k \ge 2\)，\(p\) 是奇素数，且 \(p \nmid a\)（我们暂时避开 \(p=2\) 和 \(p \mid a\) 的复杂情况）。
- 基本策略：提升解。假设我们已经有一个模 \(p\) 的解 \(x_1\)（即满足 \(x_1^n \equiv a \pmod{p}\)）。我们希望将其“提升”为模 \(p^2, p^3, \ldots, p^k\) 的解。这通常使用亨泽尔引理。
- 亨泽尔引理的应用：将方程写作 \(f(x) = x^n - a \equiv 0 \pmod{p^k}\)。设 \(x_r\) 是模 \(p^r\) 的解（\(r \ge 1\)）。我们试图找到 \(t\) 使得 \(x_{r+1} = x_r + t p^r\) 是模 \(p^{r+1}\) 的解。
代入并展开（利用泰勒展开）：
\[ f(x_{r+1}) = f(x_r + tp^r) \equiv f(x_r) + f‘(x_r) \cdot t p^r \pmod{p^{r+1}} \]
我们希望 \(f(x_{r+1}) \equiv 0 \pmod{p^{r+1}}\)。由于 \(f(x_r) \equiv 0 \pmod{p^r}\)，可设 \(f(x_r) = b p^r\)。条件化为：
\[ b p^r + f’(x_r) t p^r \equiv 0 \pmod{p^{r+1}} \iff b + f‘(x_r) t \equiv 0 \pmod{p} \]
这是一个关于 \(t\) 模 \(p\) 的线性同余方程。
3. 提升的条件与可能性：
- 如果 \(p \nmid f’(x_r)\)（即 \(n x_r^{n-1} \not\equiv 0 \pmod{p}\)），由于 \(p \nmid a\) 且 \(x_r\) 是解，必有 \(p \nmid x_r\)，所以 \(p \nmid n x_r^{n-1}\) 当且仅当 \(p \nmid n\)。在这种情况下，模 \(p\) 的线性方程有唯一解 \(t\)，从而可以从模 \(p^r\) 的每个解唯一地提升到模 \(p^{r+1}\) 的一个解。这个过程可以迭代到任意高的幂次。
- 如果 \(p \mid f‘(x_r)\)（这发生在 \(p \mid n\) 时），那么提升条件变为 \(b \equiv 0 \pmod{p}\)。如果成立，则对任意的 \(t\) 都成立，此时一个模 \(p^r\) 的解可以提升到 \(p\) 个不同的模 \(p^{r+1}\) 的解；如果不成立，则无法提升，该解在更高幂次“消亡”。
- 模 \(2^k\) 的特殊情形：模数为 2 的幂时情况更为复杂，因为 2 的原根仅在 \(k=1,2\) 时存在（原根 1, 3 模 4），对于 \(k \ge 3\) 需要使用其他生成元结构（如 5 和 -1）进行分析。通常需要单独讨论，处理过程涉及更多的分情况。
第四步：模合数 \(m\) 的解数
综合以上步骤，对于一般模数 \(m\)，设其标准分解为 \(m = 2^{k_0} \prod_{i=1}^{s} p_i^{k_i}\)（\(p_i\) 为奇素数）。方程 \(x^n \equiv a \pmod{m}\) 的解数（若存在）等于它在每个素数幂模子方程解数的乘积（由中国剩余定理保证）。
每个奇素数幂 \(p_i^{k_i}\) 下的解数，由第二步和第三步的准则决定，通常取决于：
- \(a\) 是否是模 \(p_i\) 的 \(n\) 次剩余（存在性）。
- \(\gcd(n, p_i-1)\) 的值（决定了模 \(p_i\) 的解数）。
- 对于 \(k_i > 1\)，提升过程是否唯一（取决于 \(p_i\) 是否整除 \(n\) 以及初始解的条件）。
总结核心思想
二项同余方程的解的结构，本质上由以下因素控制：
- 模数分解：中国剩余定理将其化归为素数幂情形。
- 离散对数：在模素数情形，通过原根将乘方问题转化为线性同余问题，解的存在性和个数直接由一次同余方程理论给出。
- 解的开方：模素数幂时，亨泽尔引理提供了从低次幂解系统性地构造高次幂解的方法，其可行性取决于导数在解处的值是否与模数互质。
这一理论是研究高次剩余、幂剩余符号以及更一般的指数同余方程的基础。