数论学习笔记

由于我数学一直很差，OI 里的数论就没怎么学过，所以就想系统地学一下，并写一篇博客进行总结。

由于 OI 不需要证明，所以本文中部分内容只给出了来自其他人的证明，但所有没打星号的证明都是我自己写的证明。

最大公约数

$\gcd\left(a,b\right)=\gcd\left(b,a\bmod b\right)$

int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }

（辗转相除法、欧几里得算法）

扩展欧几里得算法

裴蜀定理：若 $a,b$ 是整数，且 $\gcd(a,b)=d$，那么对于任意的整数 $x,y$，$ax+by$ 一定都是 $d$ 的倍数。特别地，一定存在 $x,y$ 满足 $ax+by=\gcd(x,y)$.

考虑求出 $ax+by=\gcd(a,b)$ 的一组解。设 $\gcd(a,b)=d,q=⌊\dfrac{a}{b}⌋,r=a\bmod b$，则有 $a=bq+r$.

假设已经求出 $bx_0+ry_0=\gcd(b,r)=d$ 的一组解。

联立，则有 $(bq+r)x+by= bx_0+ry_0$

整理，有 $b(qx+y)+rx=bx_0+ry_0$.

故 $x=y_0,y=x_0-y_0q$.

继续递归，直到 $a=d,b=0$ 时（根据欧几里得算法，一定会出现此情况），令 $x=1,y=0$.

int exgcd(int a, int b, int &x, int &y) {
	if(!b) {
		x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= x * (a / b);
}

那么如何求出 $ax+by=\gcd(a,b)$ 的所有整数解呢？

先求出任意一组解 $x=x_0, y=y_0$,

再求出 $ax+by=0$ 的一组最小整数解 $x=d_x=\dfrac{b}{\gcd(a,b)},y=d_y=-\dfrac{a}{\gcd(a,b)}$.

则所有整数解就是 $x=x_0+kd_x,y=y_0+kd_y,\ k\in\Z$.

线性组合

求方程 $a_1x_1+a_2x_2+a_3x_3+\cdots+a_nx_n=k$ 的一组解。

显然 $\gcd(a_1,a_2,\cdots,a_n)\mid k$ 是有解的充要条件。

设 $a_1x_1+a_2x_2+\cdots+a_{n-1}x_{n-1}=A\times \gcd(a_1x_1,a_2x_2,\cdots,a_{n-1}x_{n-1})$,

则有 $A\times \gcd(a_1x_1,a_2x_2,\cdots,a_{n-1}x_{n-1})+a_nx_n=k$.

使用 exgcd 求出 $A$ 和 $x_n$，再使用同样方法递归求解方程 $a_1x_1+a_2x_2+\cdots+a_{n-1}x_{n-1}=A\times \gcd(a_1x_1,a_2x_2,\cdots,a_{n-1}x_{n-1})$ 即可。

乘法逆元

若 $ax\equiv1\pmod b$, 则称 $x$ 是 $a$ 关于模 $b$ 的逆元。记为 $a^{-1}$.

上式等价于 $ax+by=1$，故由裴蜀定理，逆元存在的充要条件为 $\gcd(a,b)=1$.

显然，在 $[0,b)$ 范围中，$a$ 的乘法逆元（若存在）是唯一的。（反证法，假设有两个，推出不能都小于 $b$）

int inv(int a, int b) {
    int x, y;
    exgcd(a, b, x, y);
    if (x < 0) x += b;
    return x;
}

由欧拉定理（下文将提到）$a^{\varphi(n)}\equiv 1\pmod n$，$a^{\varphi(n)-1}$ 是 $a$ 模 $n$ 意义下的逆元。特别地，若 $n$ 为质数，由费马小定理 $a^{n-1}\equiv 1\pmod n$，$a^{n-2}$ 是 $a$ 模 $n$ 意义下的逆元，可以用快速幂求出。

如何 $O(n)$ 地求 $1\sim n$ 中所有数模质数 $p$ 的逆元呢？

递推

假设已经求出 $1\sim i-1$ 中所有数模 $p$ 的逆元，现在要求 $i$ 的逆元。

设 $q=⌊\dfrac{p}{i}⌋,r=p\bmod i$，则 $p=iq+r$，即 $iq+r\equiv 0\pmod p$.

且由于 $p$ 是质数，$r>0$，$r$ 的逆元存在。

在等式两边同时乘上 $i^{-1}r^{-1}$，则 $i^{-1}\equiv -qr^{-1}\equiv −(p/i)(p \bmod i)^{−1}\pmod p$.

由于 $p\bmod i<i$，故已经处理过，可以推出 $i^{-1}$.

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
	inv[i] = (p - p / i) * inv[p % i] % p;
}

倒推

先用 exgcd 或快速幂求出 $n!$ 的逆元。

然后通过 $((k-1)!)^{-1}\equiv k\cdot(k!)^{-1}\pmod p$ 逆推出所有阶乘的逆元。

再通过 $k^{-1}\equiv (k-1)!\cdot(k!)^{-1}\pmod p$ 就可以求出 $1\sim n$ 的逆元了。

同时，这个方法可以求出不连续的 $n$ 个整数的逆元。

线性同余方程

我们称形如 $ax\equiv c\pmod b$ 的方程为线性同余方程。

该式等价于 $ax+by=c$，因此 $\gcd(a,b)\mid c$ 为该式有整数解的充要条件。

设 $ax_0+by_0=\gcd(a,b)$，则线性同余方程的解为 $x=x_0\times \dfrac{c}{\gcd(a,b)}$.

线性同余方程组

形如

$\left\{ \begin{aligned} x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod {m_2}\\ \cdots\\ x\equiv a_n\pmod {m_n}\\ \end{aligned} \right.$

的方程组称为线性同余方程组。

中国剩余定理

对于同余方程组 $x\equiv a_i\pmod{m_i}$，若 $m_i$ 两两互质，则中国剩余定理给出了构造解的方法。且中国剩余定理断言，这个解在模 $\prod_{i=1}^nm_i$ 意义下是唯一的。

设 $M=\prod_{i=1}^nm_i,M_i=\dfrac{M}{m_i}$.

由于 $m_i$ 两两互质，则 $M_i$ 与 $m_i$ 互质。则 $M_i$ 关于模 $m_i$ 的逆元存在，设为 $t_i$.

则有 $a_iM_it_i ≡ a_i\pmod {m_i},a_iM_it_i ≡ 0\pmod {m_j}(j \ne i)$.

因此解 $x\equiv\sum_{i=1}^na_iM_it_i\pmod M$.

扩展中国剩余定理

中国剩余定理中必须要保证 $m_i$ 两两互质。而扩展中国剩余定理可以解决模数不互质的情况。

先考虑两个方程 $\left\{ \begin{aligned} x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod {m_2}\\ \end{aligned} \right.$,

转化一下，有 $x=a_1+m_1p=a_2+m_2q$，其中 $p,q\in\Z$.

即 $m_1p-m_2q=a_2-a_1$.

可以使用 exgcd 求出一组可行的 $p$ 和 $q$（或判定无解）。则 $x\equiv a_1+m_1p\pmod{\mathrm{lcm}(m_1,m_2)}$.

发现两个方程合并为了一个方程，故可以再求解多个方程组成的方程组时，可以把这些方程依次合并，直到合并到只有两个方程求解即可。

卢卡斯定理

对于质数 $p$，有

$\binom{n}{m} \bmod p=\binom {\lfloor n / p\rfloor} {\lfloor m / p\rfloor} \cdot\binom {n \bmod p} {m \bmod p} \bmod p$

于是对于模数 $p$ 较小的情况，我们可以预处理出 $1\sim p$ 的阶乘的逆元，快速求出 $\dbinom{n\bmod p}{m\bmod p}$，然后继续使用卢卡斯定理，递归求出 $\dbinom{\lfloor n / p\rfloor}{\lfloor m / p\rfloor}$ 即可。

int lucas(int n, int m) {
    if (m == 0) return 1;
    return lucas(n / p, m / p) * c(n % p, m % p) % p;
}

Lucas定理的证明*

欧拉函数

$1\sim N$ 中与 $N$ 互质的数的个数称为欧拉函数，记为 $\varphi(N)$.

欧拉函数是一个积性函数，即若 $\gcd(a,b)=1$，则 $\varphi(ab)=\varphi(a)\varphi(b)$.

积性函数证明

同时，$1\sim n$ 中有 $\lfloor \dfrac n p\rfloor$ 个数是 $p$ 的倍数。

若 $n=p^k$，$p$ 为质数，考虑排除所有 $p$ 的倍数，则 $\varphi(n)=n(\dfrac{p-1}{p})$.

由于欧拉函数是积性函数，则若 $N$ 分解质因数为 $p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$，则有 $\varphi(N)=N\times \dfrac{p_1-1}{p_1}\times\dfrac{p_2-1}{p_2}\times\cdots\times \dfrac{p_m-1}{p_m}$.

故可以使用质因数分解的方法求欧拉函数。

int phi(int n) {
	int ans = n;
    for (int i = 2; i <= sqrt(n); ++i) {
		if (n % i == 0) {
			ans = ans / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

在下文「筛法」部分中将讨论如何以 $O(n)$ 的复杂度求出 $1\sim n$ 中所有数的欧拉函数。

欧拉定理

若 $\gcd(a,n)=1$，则 $a^{\varphi(n)}\equiv 1\pmod n$.

欧拉定理证明

特别地，若 $p$ 为质数，$\gcd(a,p)=1$，则 $a^{p-1}\equiv 1\pmod p$（费马小定理）。

同时，若 $p$ 为质数，$a^p\equiv a\pmod p$ 成立不需要 $\gcd(a,p)=1$ 的条件。

扩展欧拉定理

$a^{b} \equiv\left\{\begin{array}{ll} a^{b \bmod \varphi(p)}, & \operatorname{gcd}(a, p)=1 \\ a^{b}, & \operatorname{gcd}(a, p) \neq 1, b<\varphi(p) \quad\pmod p\\ a^{b \bmod \varphi(p)+\varphi(p)}, & \operatorname{gcd}(a, p) \neq 1, b \geq \varphi(p) \end{array}\right.$

扩展欧拉定理证明*

利用扩展欧拉定理，我们可以在指数较大的情况下快速地求出 $a^b\bmod m$.

筛法

考虑一个问题：快速求不大于 $n$ 的所有质数。

一个简单的筛法叫 Eratosthenes 筛法，是从小到大遍历每个数，对于每个找到的质数，把它所有不大于 $n$ 的倍数它标为合数。则若一个数被遍历到而没有被标记，则这个数是质数。这个筛法的时间复杂度是 $O(n\log\log n)$.

int Eratosthenes(int n) {
    int p = 0;
    for (int i = 0; i <= n; ++i) is_prime[i] = 1;
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            prime[p++] = i;
            for (int j = i * i; j <= n; j += i) is_prime[j] = 0;
        }
    }
    return p;
}

一个时间复杂度更优秀的筛法叫欧拉筛（线性筛）。具体来说，还是从小到大遍历每个数，且记录每个数的最小质因子 $v$，假设已经知道第 $i$ 个数的最小质因子 $v[i]$，则枚举所有小于等于 $i$ 的质数 $p$，则 $v[i\times p]=p$. 若枚举到 $i$ 时 $f[i]$ 还未求出，则 $i$ 是质数。显然，这个筛法中每个数的 $v$ 值只会被自己的最小质因子更新一次，复杂度 $O(n)$.

for (int i = 2; i <= n; ++i) {
    if (v[i] == 0) prime[++tot] = v[i] = i;
    for (int j = 1; j <= tot; ++j) {
        if (prime[j] > v[i] || prime[j] > n / i) break;
        v[i * prime[j]] = prime[j];
    }
}

现在考虑如何用筛法求出欧拉函数。首先 Eratosthenes 筛法求欧拉函数是显然的，每个数都会被自己的所有质因子筛一遍，则在被质因子筛到时利用欧拉函数的计算公式即可。

那如何用线性筛求欧拉函数呢？先考虑欧拉函数的两个性质：

• 若质数 $p\mid n$ 且 $p^2\mid n$，则 $\varphi(n)=\varphi(\frac n p)\times p$.

  该性质可用求欧拉函数的公式证明。

• 若质数 $p\mid n$ 但 $p^2\not\mid n$，则 $\varphi(n)=\varphi(\frac n p)\times (p-1)$.

  由于欧拉函数是积性函数，且 $\gcd(\frac n p,p)=1$，故 $\varphi(n)=\varphi(\frac n p)\times \varphi(p)=\varphi(\frac n p)\times (p-1)$.

有了这两条性质后，我们就能从 $n$ 的最小质因子的欧拉函数推出 $n$ 的欧拉函数了。

phi[1] = 1;
for (int i = 2; i <= n; ++i) {
    if (v[i] == 0) prime[++tot] = v[i] = i, phi[i] = i - 1;
    for (int j = 1; j <= tot; ++j) {
        if (prime[j] > v[i] || prime[j] > n / i) break;
        v[i * prime[j]] = prime[j];
        phi[i * prime[j]] = 
            phi[i] * (i % prime[j] ? prime[j] - 1 : prime[j]);
    }
}

未完待续...（吗？不知道，还差 exLucas, BSGS, exBSGS 之类的东西）