数论复习笔记

博主： M_sea
发布时间：2021 年 04 月 05 日
1740次浏览
暂无评论
9374字数
分类：总结

阶与原根

阶

定义 1.1 (阶) 对于 $m \in \mathbb{N}^*, a \in [0, m), (a, m) = 1$，设 $n$ 为满足 $a^n \equiv 1 \pmod{m}$ 的最小正整数，则称 $n$ 为 $a$ 模 $m$ 的阶，记做 $\delta_m(a)$。

关于阶，我们给出如下定理：

定理 1.1 $a, a^2, \cdots, a^{\delta_m(a)}$ 在模 $m$ 意义下两两不同。

证明反证法。设 $i \neq j$ 且 $a^i \equiv a^j \pmod{m}$，则有 $a^{\lvert i - j \rvert} \equiv 1 \pmod{m}$，又显然有 $\lvert i - j \rvert < \delta_m(a)$，矛盾。

定理 1.2 若 $a^n \equiv 1 \pmod{m}$，则 $\delta_m(a) \mid n$。

证明反证法。设 $n = q\delta_m(a) + r$，其中 $1 \leq r < \delta_m(a)$，那么
$$
a^r \equiv a^r(a^{\delta_m(a)})^q \equiv a^n \equiv 1 \pmod{m}
$$
这与 $\delta_m(a)$ 的定义矛盾，故 $r = 0$。

定理 1.3 若 $\delta_m(a)$ 与 $\delta_m(b)$ 都存在，则 $\delta_m(ab) = \delta_m(a)\delta_m(b)$ 的充要条件是 $\gcd(\delta_m(a), \delta_m(b)) = 1$。

证明略。

定理 1.4 若 $\delta_m(a)$ 存在，设 $k \in \mathbb{N}$，则
$$
\delta_m(a^k) = \frac{\delta_m(a)}{\gcd(\delta_m(a), k)}
$$
证明我们知道 $a^{\delta_m(a)} \equiv 1 \pmod{m}$，那么
$$
(a^k)^{\frac{\delta_m(a)}{\gcd(\delta_m(a), k)}} \equiv (a^{\delta_m(a)})^{\frac{k}{\gcd(\delta_m(a), k)}} \equiv 1 \pmod{m}
$$
因此
$$
\delta_m(a^k) \mid \frac{\delta_m(a)}{\gcd(\delta_m(a), k)}
$$
另一方面，我们注意到
$$
a^{k\delta_m(a^k)} = (a^k)^{\delta_m(a^k)} \equiv 1 \pmod{m}
$$
因此
$$
\delta_m(a) \mid k\delta_m(a^k)
$$
即
$$
\frac{\delta_m(a)}{\gcd(\delta_m(a), k)} \mid \delta_m(a^k)
$$
综上即证。

原根

定义 1.2 (原根) 设 $m \in \mathbb{N}^*$，若 $\gcd(a, m) = 1$ 且 $\delta_m(a) = \varphi(m)$，则称 $a$ 为模 $m$ 的原根。

对于原根的存在性，有如下定理：

定理 1.5 $m$ 存在原根当且仅当 $m = 2, 4, p^k, 2p^k$，其中 $p$ 为奇素数，$k \in \mathbb{N}^*$。

证明略。

下面介绍求原根的方法。

定理 1.6 若 $\forall d \mid \varphi(m)$，都有 $g^{\frac{\varphi(m)}{d}} \not \equiv 1 \pmod {m}$，则 $g$ 为模 $m$ 的原根。

证明略。

于是可以枚举 $\varphi(m)$ 的约数判定，忽略快速幂复杂度为 $\mathcal{O}(\mathbf{d}(\varphi(m)))$。

定理 1.7 $m$ 的最小原根是 $m^{0.25}$ 级别的。

证明略。

因此我们可以直接从小到大枚举所有数并判定它是否为原根，这样子就可以找到一个最小原根 $g$，复杂度可以接受。

定理 1.8 设 $g$ 为模 $m$ 的任意原根，$a = g^x$，则 $a$ 为模 $m$ 的原根当且仅当 $\gcd(x, \varphi(m)) = 1$。

证明由定理 1.4 即证。

于是我们在找到最小原根后，可以枚举 $\varphi(m)$ 的所有质因数，然后筛掉其倍数。复杂度 $\mathcal{O}(\varphi(m) \log \log \varphi(m))$。

由定理 1.4，我们还可以得到以下定理：

定理 1.9 模 $m$ 的原根共有 $\varphi(\varphi(m))$ 个。

证明略。

费马小定理、欧拉定理

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

证明略。

定理 2.2 (欧拉定理) 若 $\gcd(a, p) = 1$，则 $a^{\varphi(p)} \equiv 1 \pmod{p}$。

证明略。

可以发现费马小定理实际上是欧拉定理在模数为质数时的情况。

定理 2.3 (扩展欧拉定理)
$$
a^b \equiv \begin{cases} a^{b \bmod \varphi(p)}, & \gcd(a, p) = 1 \\ a^b, & \gcd(a, p) \neq 1, b < \varphi(p) \\ a^{b \bmod \varphi(p) + \varphi(p)}, & \gcd(a, p) \neq 1, b \geq \varphi(p)\end{cases} \pmod{p}
$$
证明略。

二次剩余

本节中的 $p$ 若无特殊说明，则均指奇素数。

定义 3.1 (二次剩余) 对于非负整数 $a$，如果存在另一个非负整数 $b$ 满足 $b^2 \equiv a \pmod{p}$，则称 $a$ 为模 $p$ 的二次剩余，否则称 $a$ 为模 $p$ 的非二次剩余。

可以证明，模 $p$ 的二次剩余有恰好 $\frac{p - 1}{2}$ 个（不包括 $0$），非二次剩余有恰好 $\frac{p - 1}{2}$ 个。

定义 3.2 (勒让德符号) 定义勒让德符号
$$
\left(\frac{n}{p}\right) = \begin{cases} 1, & p \nmid n, n \text{ 是 } p \text{ 的二次剩余} \\ -1, & p \nmid n, n \text{ 不是 } p \text{ 的二次剩余 } \\ 0, & p \mid n\end{cases}
$$

定理 3.1 (欧拉判别准则)
$$
\left(\frac{n}{p}\right) \equiv n^{\frac{p - 1}{2}} \pmod{p}
$$
证明由费马小定理可知
$$
\left(n^{\frac{p - 1}{2}} - 1\right) \left(n^{\frac{p - 1}{2}} + 1\right) \equiv 0 \pmod{p}
$$
那么 $n^{\frac{p - 1}{2}}$ 模 $p$ 必为 $1$ 或 $-1$。

设 $g$ 为模 $p$ 的任意原根，$n = g^k$ 且 $k \in [0, \varphi(p))$，那么 $n^{\frac{p - 1}{2}} \equiv 1 \pmod{p}$ 相当于
$$
g^{k\frac{p - 1}{2}} \equiv 1 \pmod{p}
$$
由定理 1.2 可知 $\varphi(p) \mid k\frac{p - 1}{2}$，于是 $k$ 为偶数，则 $n$ 为二次剩余。

模 $p$ 为 $-1$ 的情况同理可证得 $n$ 为非二次剩余。

Cipolla 算法

用来快速找到 $x$ 满足 $x^2 \equiv n \pmod{p}$。

首先找到一个 $a$ 满足 $a^2 - n$ 是非二次剩余。我们可以使用随机的方式，期望两次就可以找到一个满足条件的 $a$。

然后进行扩域，定义 $i^2 = a^2 - n$，然后把所有数写成 $c + di$ 的形式，其运算法则类似于复数。

于是我们可以直接得到 $x = (a + i)^{\frac{p + 1}{2}}$。

证明首先我们给出两条引理：

引理 3.1 $(a + b)^p \equiv a^p + b^p \pmod{p}$。

二项式定理展开后即可证明，此处省略。

引理 3.2 $i^p \equiv -i \pmod{p}$。

证明
$$
\begin{aligned}
i^p & \equiv i^{p - 1} \cdot i \\
& \equiv \left(i^2\right)^{\frac{p - 1}{2}} \cdot i \\
& \equiv (a^2 - n)^{\frac{p - 1}{2}} \cdot i \\
& \equiv -i \pmod{p}
\end{aligned}
$$

有了这两条引理再加上费马小定理，即可证明上面的内容。
$$
\begin{aligned}
x^2 & \equiv (a + i)^{p + 1} \\
& \equiv (a^p + i^p) (a + i) \\
& \equiv (a - i)(a + i) \\
& \equiv a^2 - i^2 \\
& \equiv n \pmod{p}
\end{aligned}
$$

exgcd

用来求 $ax + by = \gcd(a, b)$ 的一组特解 $(x_0, y_0)$。

设 $ax_1 + by_1 = \gcd(a, b)$，$bx_2 + (a \bmod b) y_2 = \gcd(b, a \bmod b)$。于是有
$$
ax_1 + by_1 = bx_2 + (a \bmod b) y_2
$$
我们知道 $a \bmod b = a - \lfloor \frac{a}{b} \rfloor \cdot b$，那么有
$$
ax_1 + by_1 = bx_2 + (a - \lfloor \frac{a}{b} \rfloor \cdot b) y_2
$$
稍作变形得到
$$
ax_1 + by_1 = ay_2 + b(x_2 -\lfloor \frac{a}{b} \rfloor y_2)
$$
于是我们只需要递归求解 $a' = b, b' = a \bmod b$ 的子问题并得到一组解 $x', y'$，然后即可得到当前的一组解 $x = y', y = x' - \lfloor\frac{a}{b}\rfloor y'$。边界是 $a = 1, b = 0$，此时令 $x = 1, y = 0$ 即可。

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

解二元一次不定方程

更一般的情况是解二元一次不定方程 $ax + by = c$。根据裴蜀定理，该不定方程有解当且仅当 $c \mid \gcd(a, b)$。

记 $d = \gcd(a, b)$，考虑先求出 $ax + by = d$ 的一组特解 $(x_0, y_0)$，于是原方程的一组特解为
$$
\begin{cases} x_1 = \frac{x_0c}{d} \\ y_1 = \frac{y_0c}{d}\end{cases}
$$
进而得到原方程的通解为
$$
\begin{cases} x = x_1 + k\frac{b}{d} \\ y = y_1 - k\frac{a}{d}\end{cases}, k \in \mathbb{Z}
$$

求逆元

我们要求 $ax \equiv 1 \pmod{m}$，这相当于解一个不定方程 $ax + km = 1$。

CRT / exCRT

用来解线性同余方程组 $\begin{cases} x \equiv a_1 \pmod{b_1} \\ \vdots \\ x \equiv a_k \pmod{b_k}\end{cases}$ 的最小非负整数解。

CRT

在 $b_1, b_2, \cdots, b_k$ 两两互质时才能使用。

设 $M = \prod_{i = 1}^k b_i$，$m_i = \frac{M}{b_i}$，$m_i^{-1}$ 为 $m_i$ 在模 $b_i$ 意义下的逆元，那么方程组的一个解为
$$
\sum_{i = 1}^k a_im_im_i^{-1}
$$
不难验证其对于每个方程都成立。另外可以证明方程组在 $[0, M)$ 内有唯一解，所以只需要对 $M$ 取模即可得到最小非负整数解。

实际上可以令 $M = \operatorname{lcm}(b_1, b_2, \cdots, b_k)$，仍然成立。

exCRT

和 CRT 其实没有什么相似的地方，它基于对同余方程的合并。

考虑两个同余方程
$$
\begin{cases} x \equiv a_1 \pmod{b_1} \\ x \equiv a_2 \pmod{b_2}\end{cases}
$$
我们可以把 $x$ 写成 $a_1 + kb_1$，那么相当于解 $a_1 + kb_1 \equiv a_2 \pmod{b_2}$，即 $kb_1 \equiv a_2 - a_1 \pmod{b_2}$。使用 exgcd 可以解出 $k$，然后合并为 $x \equiv a_1 + kb_1 \pmod{\operatorname{lcm}(b_1, b_2)}$ 即可。

重复做这个过程 $k - 1$ 次，即可得出原方程组的解。

BSGS / exBSGS

BSGS

用来求解离散对数，即求 $a^x \equiv b \pmod{p}$，但是要求 $\gcd(a, p) = 1$。

设 $S = \lceil \sqrt{p} \rceil$，并设 $x = AS - B$，其中 $B < S$。

那么原方程可以化为
$$
a^{AS} \equiv b\cdot A^B \pmod{p}
$$
枚举 $B$ 并将所有的$b^B$ 存入一个哈希表中，然后枚举 $A$ 判断哈希表中是否存在对应元素即可。

当然 $x^a \equiv b \pmod{p}$ 也是可以解的，化为 $g^{ka} \equiv b \pmod{p}$ 即可。

exBSGS

用来解决 $\gcd(a, p) \neq 1$ 的情况，主要思想是通过一些变换把 $a, p$ 变得互质。

设 $d_1 = \gcd(a, p)$，如果 $d_1 \nmid b$ 则无解，否则原方程化为
$$
\frac{a}{d_1} a^{x - 1}\equiv \frac{b}{d_1} \pmod{\frac{p}{d_1}}
$$
如果 $\gcd(a, \frac{p}{d_1}) \neq 1$，我们就再设 $d_2 = \gcd(a, \frac{p}{d_2})$，然后做上面的过程。

这样子最后会得到
$$
\frac{a}{d_1d_2\cdots d_k} a^{x - k} \equiv \frac{b}{d_1d_2\cdots d_k} \pmod{\frac{p}{d_1d_2\cdots d_k}}
$$
此时 $\frac{a}{d_1d_2\cdots d_k}$ 存在逆元，因此可以直接移到右边，然后 BSGS 即可。

注意可能有解 $<k$ 的情况，可以先 $\mathcal{O}(k)$ 枚举一遍判断。

Lucas / exLucas

Lucas 定理

定理 7.1 (Lucas 定理) 设 $p$ 为质数，则
$$
{n \choose m} \equiv {\lfloor n / p \rfloor \choose \lfloor m / p \rfloor} {n \bmod p \choose m \bmod p} \pmod{p}
$$
证明略。

于是我们可以把 ${n \choose m}$ 拆成 $\log_p n$ 个上下标在 $p$ 以内的组合数的积。

exLucas

用来处理 $p$ 不是质数的情况。

// 太毒瘤了，咕了

Miller-Rabin

Miller Rabin 算法依赖于以下两个东西：

费马测试：若某个整数 $a \in [2, n - 1]$ 满足 $a^{n - 1} \not \equiv 1 \pmod{n}$，说明 $n$ 不为质数。
二次探测：若 $p$ 是奇素数，则 $x^2 \equiv 1 \pmod{p}$ 的解为 $1$ 或 $p - 1$。

于是可以得到如下测试方法：将 $n - 1$ 分解为 $n' \times 2^l$，然后进行若干次测试，每次随机生成 $a \in [2, n - 1]$ 然后计算 $a^{n'}$，并进行至多 $l$ 次平方操作，判断其是否出现了非平凡根。

好像 $61$ 和 $24251$ 的正确率很高，但是最好还是多判几个质数。

Pollard-Rho

不想写了，见这里

数论函数相关

积性函数

定义 8.1 (积性函数) 若数论函数 $\mathbf{f}$ 满足对于任意的 $a, b \in \mathbb{N}^*, \gcd(a, b) = 1$，都有 $\mathbf{f}(ab) = \mathbf{f}(a)\mathbf{f}(b)$，则称 $\mathbf{f}$ 为积性函数。

特别的，如果对于任意的 $a, b \in \mathbb{N}^*$ 都满足上面的条件，则称 $\mathbf{f}$ 为完全积性函数。

常见的积性函数有 $\epsilon, \mathbf{1}, \mathbf{id}, \mu, \varphi, \mathbf{d}, \sigma_k$ 等，其中前 $3$ 个还是完全积性函数。

狄利克雷卷积

定义 8.2 (狄利克雷卷积) 定义两个数论函数的狄利克雷卷积 $\mathbf{h} = \mathbf{f} * \mathbf{g}$ 为
$$
\mathbf{h}(n) = \sum_{d \mid n} \mathbf{f}(d) \mathbf{g}\left(\frac{n}{d}\right)
$$

狄利克雷卷积满足交换律、结合律和对加法的分配律。

可以证明，两个积性函数的狄利克雷卷积也为积性函数。

常见的一些狄利克雷卷积有

$\mathbf{f} * \epsilon = \mathbf{f}$。
$\epsilon = \mathbf{1} * \mu$。
$\mathbf{d} = \mathbf{1} * \mathbf{1}$。
$\varphi = \mu * \mathbf{id}$。

莫比乌斯反演

其实就是 $\mathbf{f} = \mathbf{g} * \mathbf{1} \Leftrightarrow \mathbf{g} = \mathbf{f} * \mu$。~~网上一些文章写的很复杂，其实就是吓唬人的（~~

杜教筛

见这里

Min_25 筛

见这里

最后修改：2021 年 04 月 09 日 11 : 20 AM

发表评论取消回复

评论 *

私密评论

名称 *

邮箱 *

地址

洛谷5176 公约数
浏览次数: 25654
HNOI2019 ～Zero～
浏览次数: 25436
APIO2020 ～Intermezzo～
浏览次数: 14624
～After OI～
浏览次数: 14552
CSP2019 ～Idle Dream～
浏览次数: 9924

草莓奶昔
一直在研究这道题，难得有这么好的码风，感谢楼主!!!
konjacq
巨佬M_sea的AFO就是去搞ACM吗orz
xgzc
现在已经拿到满意的成绩了
Qihoo360
orz
智子
突然想起我小学时也是在白老师那里学的（

数论复习笔记

M_sea • 2021 年 04 月 05 日

阶与原根

阶

定义 1.1 (阶) 对于 $m \in \mathbb{N}^*, a \in [0, m), (a, m) = 1$，设 $n$ 为满足 $a^n \equiv 1 \pmod{m}$ 的最小正整数，则称 $n$ 为 $a$ 模 $m$ 的阶，记做 $\delta_m(a)$。

关于阶，我们给出如下定理：

定理 1.1 $a, a^2, \cdots, a^{\delta_m(a)}$ 在模 $m$ 意义下两两不同。

证明反证法。设 $i \neq j$ 且 $a^i \equiv a^j \pmod{m}$，则有 $a^{\lvert i - j \rvert} \equiv 1 \pmod{m}$，又显然有 $\lvert i - j \rvert < \delta_m(a)$，矛盾。

定理 1.2 若 $a^n \equiv 1 \pmod{m}$，则 $\delta_m(a) \mid n$。

证明反证法。设 $n = q\delta_m(a) + r$，其中 $1 \leq r < \delta_m(a)$，那么
$$
a^r \equiv a^r(a^{\delta_m(a)})^q \equiv a^n \equiv 1 \pmod{m}
$$
这与 $\delta_m(a)$ 的定义矛盾，故 $r = 0$。

定理 1.3 若 $\delta_m(a)$ 与 $\delta_m(b)$ 都存在，则 $\delta_m(ab) = \delta_m(a)\delta_m(b)$ 的充要条件是 $\gcd(\delta_m(a), \delta_m(b)) = 1$。

证明略。

定理 1.4 若 $\delta_m(a)$ 存在，设 $k \in \mathbb{N}$，则
$$
\delta_m(a^k) = \frac{\delta_m(a)}{\gcd(\delta_m(a), k)}
$$
证明我们知道 $a^{\delta_m(a)} \equiv 1 \pmod{m}$，那么
$$
(a^k)^{\frac{\delta_m(a)}{\gcd(\delta_m(a), k)}} \equiv (a^{\delta_m(a)})^{\frac{k}{\gcd(\delta_m(a), k)}} \equiv 1 \pmod{m}
$$
因此
$$
\delta_m(a^k) \mid \frac{\delta_m(a)}{\gcd(\delta_m(a), k)}
$$
另一方面，我们注意到
$$
a^{k\delta_m(a^k)} = (a^k)^{\delta_m(a^k)} \equiv 1 \pmod{m}
$$
因此
$$
\delta_m(a) \mid k\delta_m(a^k)
$$
即
$$
\frac{\delta_m(a)}{\gcd(\delta_m(a), k)} \mid \delta_m(a^k)
$$
综上即证。

原根

定义 1.2 (原根) 设 $m \in \mathbb{N}^*$，若 $\gcd(a, m) = 1$ 且 $\delta_m(a) = \varphi(m)$，则称 $a$ 为模 $m$ 的原根。

对于原根的存在性，有如下定理：

定理 1.5 $m$ 存在原根当且仅当 $m = 2, 4, p^k, 2p^k$，其中 $p$ 为奇素数，$k \in \mathbb{N}^*$。

证明略。

下面介绍求原根的方法。

定理 1.6 若 $\forall d \mid \varphi(m)$，都有 $g^{\frac{\varphi(m)}{d}} \not \equiv 1 \pmod {m}$，则 $g$ 为模 $m$ 的原根。

证明略。

于是可以枚举 $\varphi(m)$ 的约数判定，忽略快速幂复杂度为 $\mathcal{O}(\mathbf{d}(\varphi(m)))$。

定理 1.7 $m$ 的最小原根是 $m^{0.25}$ 级别的。

证明略。

因此我们可以直接从小到大枚举所有数并判定它是否为原根，这样子就可以找到一个最小原根 $g$，复杂度可以接受。

定理 1.8 设 $g$ 为模 $m$ 的任意原根，$a = g^x$，则 $a$ 为模 $m$ 的原根当且仅当 $\gcd(x, \varphi(m)) = 1$。

证明由定理 1.4 即证。

于是我们在找到最小原根后，可以枚举 $\varphi(m)$ 的所有质因数，然后筛掉其倍数。复杂度 $\mathcal{O}(\varphi(m) \log \log \varphi(m))$。

由定理 1.4，我们还可以得到以下定理：

定理 1.9 模 $m$ 的原根共有 $\varphi(\varphi(m))$ 个。

证明略。

费马小定理、欧拉定理

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

证明略。

定理 2.2 (欧拉定理) 若 $\gcd(a, p) = 1$，则 $a^{\varphi(p)} \equiv 1 \pmod{p}$。

证明略。

可以发现费马小定理实际上是欧拉定理在模数为质数时的情况。

定理 2.3 (扩展欧拉定理)
$$
a^b \equiv \begin{cases} a^{b \bmod \varphi(p)}, & \gcd(a, p) = 1 \\ a^b, & \gcd(a, p) \neq 1, b < \varphi(p) \\ a^{b \bmod \varphi(p) + \varphi(p)}, & \gcd(a, p) \neq 1, b \geq \varphi(p)\end{cases} \pmod{p}
$$
证明略。

二次剩余

本节中的 $p$ 若无特殊说明，则均指奇素数。

定义 3.1 (二次剩余) 对于非负整数 $a$，如果存在另一个非负整数 $b$ 满足 $b^2 \equiv a \pmod{p}$，则称 $a$ 为模 $p$ 的二次剩余，否则称 $a$ 为模 $p$ 的非二次剩余。

可以证明，模 $p$ 的二次剩余有恰好 $\frac{p - 1}{2}$ 个（不包括 $0$），非二次剩余有恰好 $\frac{p - 1}{2}$ 个。

定义 3.2 (勒让德符号) 定义勒让德符号
$$
\left(\frac{n}{p}\right) = \begin{cases} 1, & p \nmid n, n \text{ 是 } p \text{ 的二次剩余} \\ -1, & p \nmid n, n \text{ 不是 } p \text{ 的二次剩余 } \\ 0, & p \mid n\end{cases}
$$

定理 3.1 (欧拉判别准则)
$$
\left(\frac{n}{p}\right) \equiv n^{\frac{p - 1}{2}} \pmod{p}
$$
证明由费马小定理可知
$$
\left(n^{\frac{p - 1}{2}} - 1\right) \left(n^{\frac{p - 1}{2}} + 1\right) \equiv 0 \pmod{p}
$$
那么 $n^{\frac{p - 1}{2}}$ 模 $p$ 必为 $1$ 或 $-1$。

设 $g$ 为模 $p$ 的任意原根，$n = g^k$ 且 $k \in [0, \varphi(p))$，那么 $n^{\frac{p - 1}{2}} \equiv 1 \pmod{p}$ 相当于
$$
g^{k\frac{p - 1}{2}} \equiv 1 \pmod{p}
$$
由定理 1.2 可知 $\varphi(p) \mid k\frac{p - 1}{2}$，于是 $k$ 为偶数，则 $n$ 为二次剩余。

模 $p$ 为 $-1$ 的情况同理可证得 $n$ 为非二次剩余。

Cipolla 算法

用来快速找到 $x$ 满足 $x^2 \equiv n \pmod{p}$。

首先找到一个 $a$ 满足 $a^2 - n$ 是非二次剩余。我们可以使用随机的方式，期望两次就可以找到一个满足条件的 $a$。

然后进行扩域，定义 $i^2 = a^2 - n$，然后把所有数写成 $c + di$ 的形式，其运算法则类似于复数。

于是我们可以直接得到 $x = (a + i)^{\frac{p + 1}{2}}$。

证明首先我们给出两条引理：

引理 3.1 $(a + b)^p \equiv a^p + b^p \pmod{p}$。

二项式定理展开后即可证明，此处省略。

引理 3.2 $i^p \equiv -i \pmod{p}$。

证明
$$
\begin{aligned}
i^p & \equiv i^{p - 1} \cdot i \\
& \equiv \left(i^2\right)^{\frac{p - 1}{2}} \cdot i \\
& \equiv (a^2 - n)^{\frac{p - 1}{2}} \cdot i \\
& \equiv -i \pmod{p}
\end{aligned}
$$

有了这两条引理再加上费马小定理，即可证明上面的内容。
$$
\begin{aligned}
x^2 & \equiv (a + i)^{p + 1} \\
& \equiv (a^p + i^p) (a + i) \\
& \equiv (a - i)(a + i) \\
& \equiv a^2 - i^2 \\
& \equiv n \pmod{p}
\end{aligned}
$$

exgcd

用来求 $ax + by = \gcd(a, b)$ 的一组特解 $(x_0, y_0)$。

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

解二元一次不定方程

更一般的情况是解二元一次不定方程 $ax + by = c$。根据裴蜀定理，该不定方程有解当且仅当 $c \mid \gcd(a, b)$。

求逆元

我们要求 $ax \equiv 1 \pmod{m}$，这相当于解一个不定方程 $ax + km = 1$。

CRT / exCRT

用来解线性同余方程组 $\begin{cases} x \equiv a_1 \pmod{b_1} \\ \vdots \\ x \equiv a_k \pmod{b_k}\end{cases}$ 的最小非负整数解。

CRT

在 $b_1, b_2, \cdots, b_k$ 两两互质时才能使用。

实际上可以令 $M = \operatorname{lcm}(b_1, b_2, \cdots, b_k)$，仍然成立。

exCRT

和 CRT 其实没有什么相似的地方，它基于对同余方程的合并。

重复做这个过程 $k - 1$ 次，即可得出原方程组的解。

BSGS / exBSGS

BSGS

用来求解离散对数，即求 $a^x \equiv b \pmod{p}$，但是要求 $\gcd(a, p) = 1$。

设 $S = \lceil \sqrt{p} \rceil$，并设 $x = AS - B$，其中 $B < S$。

那么原方程可以化为
$$
a^{AS} \equiv b\cdot A^B \pmod{p}
$$
枚举 $B$ 并将所有的$b^B$ 存入一个哈希表中，然后枚举 $A$ 判断哈希表中是否存在对应元素即可。

当然 $x^a \equiv b \pmod{p}$ 也是可以解的，化为 $g^{ka} \equiv b \pmod{p}$ 即可。

exBSGS

用来解决 $\gcd(a, p) \neq 1$ 的情况，主要思想是通过一些变换把 $a, p$ 变得互质。

注意可能有解 $<k$ 的情况，可以先 $\mathcal{O}(k)$ 枚举一遍判断。

Lucas / exLucas

Lucas 定理

定理 7.1 (Lucas 定理) 设 $p$ 为质数，则
$$
{n \choose m} \equiv {\lfloor n / p \rfloor \choose \lfloor m / p \rfloor} {n \bmod p \choose m \bmod p} \pmod{p}
$$
证明略。

于是我们可以把 ${n \choose m}$ 拆成 $\log_p n$ 个上下标在 $p$ 以内的组合数的积。

exLucas

用来处理 $p$ 不是质数的情况。

// 太毒瘤了，咕了

Miller-Rabin

Miller Rabin 算法依赖于以下两个东西：

费马测试：若某个整数 $a \in [2, n - 1]$ 满足 $a^{n - 1} \not \equiv 1 \pmod{n}$，说明 $n$ 不为质数。
二次探测：若 $p$ 是奇素数，则 $x^2 \equiv 1 \pmod{p}$ 的解为 $1$ 或 $p - 1$。

好像 $61$ 和 $24251$ 的正确率很高，但是最好还是多判几个质数。

Pollard-Rho

不想写了，见这里

数论函数相关

积性函数

定义 8.1 (积性函数) 若数论函数 $\mathbf{f}$ 满足对于任意的 $a, b \in \mathbb{N}^*, \gcd(a, b) = 1$，都有 $\mathbf{f}(ab) = \mathbf{f}(a)\mathbf{f}(b)$，则称 $\mathbf{f}$ 为积性函数。

特别的，如果对于任意的 $a, b \in \mathbb{N}^*$ 都满足上面的条件，则称 $\mathbf{f}$ 为完全积性函数。

常见的积性函数有 $\epsilon, \mathbf{1}, \mathbf{id}, \mu, \varphi, \mathbf{d}, \sigma_k$ 等，其中前 $3$ 个还是完全积性函数。

狄利克雷卷积

定义 8.2 (狄利克雷卷积) 定义两个数论函数的狄利克雷卷积 $\mathbf{h} = \mathbf{f} * \mathbf{g}$ 为
$$
\mathbf{h}(n) = \sum_{d \mid n} \mathbf{f}(d) \mathbf{g}\left(\frac{n}{d}\right)
$$

狄利克雷卷积满足交换律、结合律和对加法的分配律。

可以证明，两个积性函数的狄利克雷卷积也为积性函数。

常见的一些狄利克雷卷积有

$\mathbf{f} * \epsilon = \mathbf{f}$。
$\epsilon = \mathbf{1} * \mu$。
$\mathbf{d} = \mathbf{1} * \mathbf{1}$。
$\varphi = \mu * \mathbf{id}$。

莫比乌斯反演

其实就是 $\mathbf{f} = \mathbf{g} * \mathbf{1} \Leftrightarrow \mathbf{g} = \mathbf{f} * \mu$。~~网上一些文章写的很复杂，其实就是吓唬人的（~~

杜教筛

见这里

Min_25 筛

见这里

阶与原根

阶

原根

费马小定理、欧拉定理

二次剩余

Cipolla 算法

exgcd

解二元一次不定方程

求逆元

CRT / exCRT

CRT

exCRT

BSGS / exBSGS

BSGS

exBSGS

Lucas / exLucas

Lucas 定理

exLucas

Miller-Rabin

Pollard-Rho

数论函数相关

积性函数

狄利克雷卷积

莫比乌斯反演

杜教筛

Min_25 筛

发表评论 取消回复

数论复习笔记

阶与原根

阶

原根

费马小定理、欧拉定理

二次剩余

Cipolla 算法

exgcd

解二元一次不定方程

求逆元

CRT / exCRT

CRT

exCRT

BSGS / exBSGS

BSGS

exBSGS

Lucas / exLucas

Lucas 定理

exLucas

Miller-Rabin

Pollard-Rho

数论函数相关

积性函数

狄利克雷卷积

莫比乌斯反演

杜教筛

Min_25 筛

发表评论取消回复