同余类数论学习

Hardsoft

2026-05-07

学习记录

中国剩余定理, 卢卡斯定理, 大步小步, 扩展欧几里德, 数论, 阶和原根, 高次剩余

$$ \def\ord{\operatorname{Ord}} $$

扩展欧几里德算法 (exgcd)

扩展欧几里德是对 $\gcd$ 辗转相除法的扩展，使其可以求解二元一次不定方程 $ax+by=\gcd(a,b)$ 的一组特解 $(x_0,y_0)$．

函数定义是 exgcd(a, b, &x, &y)，调用传 b, a%b，边界是 b==0．

template<typename Tp> Tp exgcd(Tp a, Tp b, Tp& x, Tp& y) {
    if (b == 0) { x = 1, y = 0; return a; }
    Tp g = exgcd(b, a % b, x, y);
    std::tie(x, y) = std::make_tuple(y, x - a/b * y);
    return g;
}

注意到边界的时候，我们有 $\gcd(a,0)=a$，求解 $ax+0y=a$ 显然有特解 $(x,y) = (1,0)$．

运算过程中，我们传进去 $(x,y)$，得到了解 $$b \cdot x' + (a - \lfloor \dfrac a b \rfloor b) \cdot y' = \gcd(a,b)$$ 我们现在想要得到一个 $$ax+by=\gcd(a,b)$$ 的特解，联立上式可以得到 $$b \cdot x' + (a - \lfloor \dfrac a b \rfloor b) \cdot y' = ax+by$$进行整理可以得到 $$a \cdot y' + b \cdot (x' - \lfloor \dfrac a b \rfloor \cdot y') = ax + by $$易于看出 $$ \begin{cases} x = y' \\ y = x' - \lfloor \dfrac a b \rfloor \cdot y' \end{cases} $$

中国剩余定理 (CRT)

这个解法适用于求解 $\begin{cases} x \equiv a_1 \pmod{m_1} \\ \ddots \\ x \equiv a_k \pmod{m_k} \end{cases}$ 且所有模数都互素时的 $x$ 的通解．

先讲结论，设 $$M=\prod_{i=1}^k m_i \qquad M_i=\frac{M}{m_i}$$ $$M_i \cdot {M_i}^{-1} \equiv 1 \pmod{m_i} $$ 则有 $x$ 的通解 $$x \equiv \sum_{i=1}^k a_i \cdot M_i \cdot {M_i}^{-1} \pmod{M}$$

证明是显然的，因为对于每一组，只有求和式的第 $i$ 项有贡献，其余同余意义下都是 $0$．

扩展中国剩余定理 (exCRT)

同样求解上式，但是模数不是互素的．

考虑合并两个式子 $$\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \end{cases} \implies x = m_1x_1 + a_1 = m_2x_2 + a_2 \implies m_1x_1 - m_2x_2 = a_2 - a_1$$

由 $\text{exgcd}$ 可以求得一组解，但是如果 $\bm{\gcd(m_1,m_2) \nmid a_2-a_1}$，那就是无解了．注意求出解之后还要将解扩大 $\dfrac{a_2-a_1}{\gcd(m_1,m_2)}$ 倍．

合并之后就变成了一个式子 $x \equiv m_1x_1 + a_1 \pmod{\operatorname{lcm}(m_1,m_2)}$．不断合并就可以了．

大步小步 (BSGS)

考虑求解以下离散对数方程：$ a^x \equiv b \pmod m $，保证 $\bm{(a,m)=1}$．

先看一个引理，写出 $a^0, a^1, a^2, \dots$ 可以用抽屉原理证明循环节长度不超过 $m$．
得到这个引理，我们已经可以直接枚举 $x\in[0,m)$ 找出一个特解了．
但是这还不够，我们要 $\sqrt m$ 的时间复杂度，考虑对枚举的部分进行分块，块长为 $k=\sqrt m$．这意味着每次枚举的 $x$ 可以写成 $ik - j$，其中 $i,j \in [0,k)$．那么写出来形式就是 $a^{ik} \equiv a^j b \pmod m$，发现两边实际上是哈希表匹配．于是使用哈希表预处理，理论时空复杂度 $O(\sqrt m)$．

注意：这里实际上隐含地引入了逆元的概念，而 $(a,m) \ne 1$ 的时候没有逆元．

想得到通解，还需要一个引理：当 $(a,m)=1$ 的时候，循环节长度为 $\ord_m(a)$．这个后面会讲．

扩展大步小步 (exBSGS)

仍然考虑 $a^x \equiv b \pmod m$，但是没有任何保证．

写成 $a^x + my = b$ 的形式，然后想怎么把 $a$ 和 $m$ 弄成互素的．现在同时除以 $d_1=\gcd(a, m)$ 得到 $$\frac{a}{d_1} a^{x-1} + \frac{m}{d_1}y = \frac{b}{d_1}$$ 如果现在的 $\gcd(a,\dfrac{m}{d_1}) \ne 1$ 的话，那就继续同时除以 $d_2=\gcd(a,\dfrac{m}{d_1})$，得到 $$\frac{a^2}{d_1d_2}a^{x-2} + \frac{m}{d_1d_2}y = \frac{b}{d_1d_2}$$ 以此类推，直到 $\gcd(a,\dfrac{m}{d_1d_2 \cdots d_n})=1$．我们令 $\displaystyle D=\prod_{i=1}^n d_i$，此时原问题化为 $$\begin{aligned} \frac{a^n}{D}a^{x-n} + \frac{m}{D}y &= \frac{b}{D} \\ \frac{a^n}{D} a^{x-n} &\equiv \frac{b}{D} \pmod{\frac{m}{D}} \\ a^{x-n} &\equiv \frac{b}{a^n} \pmod{\frac m D} \end{aligned}$$ 这就是一个标准的 BSGS 问题了，直接解就可以了．

如果 $\bm{D \nmid b}$，原问题无解．

不要忘记枚举 $\bm{x \in [0,n)}$ 了！

高次剩余

求解 $x^a \equiv b \pmod m$，保证了 $m$ 为质数．

阶和原根

以下给定的 $a$ 与 $m$ 互素．

阶的定义：称 $\ord_m(a)$为最小的正整数使得 $a^n \equiv 1 \pmod m$．

原根的定义：称 $g$ 为 $\bmod m$ 下的原根，当且仅当 $\ord_m(g)=\varphi(m)$．

有原根的性质和判定定理：原根 $g$ $\iff$ 对于 $\varphi(m)$ 的每个素因子 $p$，都有 $g^{\frac{\varphi(m)}{p}} \not\equiv 1 \pmod m$．

特别的，当 $m$ 为质数的时候，$g^0, g^1, g^2, \cdots, g^{m-2}$ 构成一个 $1 \sim m-1$ 的排列．

通过原根我们可以尝试将高次剩余问题转化为大步小步模型．

显然如果 $a=0,b=0$ 时，$x$ 无解。
如果 $a\ne 0,b=0$ 时，$x=0$。
对于解 $x \in [1,m)$ 的情况，设 $x=g^y$，$y \in [0, m-1)$。我们立刻知道，$g^y$ 可以表示所有的 $x$。

所以我们不妨先解出 $g^y \equiv b \cdot g^{-a} \pmod m$，然后令 $x=g^y$ 就得到了一个解。