前言
我曾今写过一篇标题一模一样的文章，但是那篇都是在抄书，写的太烂了。
在此重构。
模意义是什么？
即小学学过的"余数"：\(13\) 除以 \(5\) 商 \(2\) 余 \(3\)。那么 \(13 \bmod 5 = 3\)（\(\bmod\) 读作模）。
如果有两个数 \(a,b\) 除以一个数 \(p\) 的余数一样，则我们称 \(a,b\) 关于 \(p\) 同余。记作：
\[a \equiv b \pmod p \]在上下文清晰时，为了方便，可能省略 \(\pmod p\)，直接记作 \(a \equiv b\)。
在模意义下，同余的数就是同一个数。例如，模 \(3\) 意义下，\(1,4,7,-2\) 这些数统统都是同一个数。
举例：
- \(4 + 5 \equiv 2 \pmod 7\)。
- 注：\(4 + 5 = 9\)。\(9 \bmod 7 = 2\)。
- \(4 - 5 \equiv 6 \pmod 7\)。
- 注：\(4 - 5 = -1\)。\((-1) \bmod 7 = 6\)。
- \(5 \times 6 \equiv 2 \pmod 7\)。
- 注：\(5 \times 6 = 30\)。\(30 \bmod 7 = 2\)。
加法、减法、乘法都很简单。
前置知识 与 符号约定
\(\gcd\) 为最大公约数。\(\text{lcm}\) 为最小公倍数。
\(a|b\) 表示 \(a\) 能整除 \(b\)。例：\(2|6\)。
\(a \perp b\) 表示 \(a\) 与 \(b\) 互质。例：\(8 \perp 9\)。
艾弗森括号 \([c]\) 表示：\([c] = \begin{cases} 1 & c \\ 0 & \lnot c\end{cases}\)（\(\lnot\) 表示逻辑非）。
【定义】\(m\) 的缩系：所有与模数 \(m\) 互质的数的集合。
【定理】同余的除法性质 1：在模 \(m\) 意义下，若 \(a \perp m\) 且 \(ax \equiv ay\)，则 \(x \equiv y\)。
证明：反证法。留作练习。\(\square\)
【定理】裴蜀定理：关于 \(x,y\) 的方程 \(ax+by=c\) 有解，当且仅当 \(\gcd(a,b) | c\)。
注：形如 \(ax+by=c\) 的方程可使用 exgcd 在 \(O(\log n)\) 时间求解。（[Luogu P5656]【模板】二元一次不定方程 (exgcd)）
【定义】欧拉函数：\(\varphi(n) = \sum\limits_{i=1}^n [i \perp n]\)。
对于质数 \(p\) 有 \(\varphi(p) = p-1\)。
除法？（乘法逆元）
观察
思考：模 \(7\) 意义下，\(\dfrac 1 4\) 是几？
思考 \(\dfrac 1 4\) 的本质是什么。设它为 \(x\)，不管 \(x\) 是多少，理应满足 \(4x \equiv 1 \pmod 7\)。
我们惊人地发现，\(x \equiv 2 \pmod 7\) 是唯一解。所以：\(\dfrac 1 4 \equiv 2\)。
再思考：模 \(7\) 意义下，\(\dfrac 3 4\) 是几？
答案：\(\dfrac 3 4 \equiv 3 \times \dfrac 1 4 \equiv 3 \times 2 \equiv 6\)。
【定义】乘法逆元：模 \(m\) 意义下，\(x\) 的乘法逆元 \(y\) 满足 \(x \times y \equiv 1 \pmod m\)。简称逆元。
【定理】逆元存在条件：\(a\) 有乘法逆元当且仅当 \(a\) 属于 \(m\) 的缩系。
证明：见下文计算方法 2。
【定理】逆元的唯一性：模 \(m\) 意义下，\(x\) 的乘法逆元若存在则唯一。
证明：由同余的除法性质 1 与逆元存在条件直接推出。\(\square\)
除以 \(x\) 相当于乘上 \(x\) 的逆元。
如何计算？
计算方法 1：费马小定理
仅适用于模数为质数。
【定理】费马小定理：模数 \(p\) 为质数，\(a \not\equiv 0\)，则：
\[a^{p-1} \equiv 1 \pmod p \]证明：
定义集合 \(A=\{1,2,\dots,p-1\}\)。
把集合 \(A\) 的每个数乘上 \(a\) 得到集合 \(B\)。
根据同余的除法性质 1 可得 \(A=B\)。把两个集合里的数乘起来：\(\prod\limits_{i=1}^{p-1} A_i \equiv \prod\limits_{i=1}^{p-1} a A_i = a^{p-1} \prod\limits_{i=1}^{p-1} A_i\)。
根据同余的除法性质 1 可得 \(a^{p-1} \equiv 1\)。\(\square\)
由费马小定理可以得到：
\[\dfrac 1 a \equiv a^{p-2} \]因此，\(\dfrac a b \equiv a \times b^{p-2} \pmod p\)。
计算方法 2：二元一次不定方程
\(a \times b \equiv 1 \pmod m\) 相当于 \(ab + mk = 1\)。\(a,m\) 都已知，可以求出 \(b\)。
由裴蜀定理可知：
【定理】逆元存在条件：\(a\) 有乘法逆元当且仅当 \(a\) 属于 \(m\) 的缩系。
例题 1：乘法逆元的应用
[Luogu P4942] 小凯的数字：已知 \(M\)，在模 \(9\) 意义下求 \(\dfrac M 2\) 的值。
因为 \(2 \times 5 \equiv 1\)，所以 \(\dfrac 1 2 \equiv 5\)，所以答案为 \(5M\)。
重要概念：欧拉定理
是费马小定理的拓展。
【定理】欧拉定理：模 \(m\) 意义下，\(a \perp m\)，则：
\[a^{\varphi(m)} \equiv 1 \pmod m \]证明：
定义集合 \(A\) 为 \(m\) 的缩系。
把集合 \(A\) 的每个数乘上 \(a\) 得到集合 \(B\)。
根据同余的除法性质 1 可得 \(A=B\)。把两个集合里的数乘起来：\(\prod\limits_{i=1}^{\varphi(m)} A_i \equiv \prod\limits_{i=1}^{\varphi(m)} a A_i = a^{\varphi(m)} \prod\limits_{i=1}^{\varphi(m)} A_i\)。
根据同余的除法性质 1 可得 \(a^{\varphi(m)} \equiv 1\)。\(\square\)
重要概念：CRT
[Luogu P1495]【模板】中国剩余定理（CRT）/ 曹冲养猪
解方程：
\[\begin{cases} x \equiv r_1 \pmod {m_1} \\ x \equiv r_2 \pmod {m_2} \\ \vdots \\ x \equiv r_n \pmod {m_n} \end{cases}\]其中 \(m_{1 \sim n}\) 不一定是质数，但是两两互质。
（注：不互质其实也能做，但是用途不多：[Luogu P4777]【模板】扩展中国剩余定理（EXCRT））
【定理】中国剩余定理（CRT）：对于这样的同余方程组，设 \(M = \prod\limits_{i=1}^n m_i\)，\(M_i = \dfrac M {m_i}\)。设 \(t_i \equiv \dfrac 1 {M_i} \pmod {m_i}\)（即 \(t_i M_i \equiv 1 \pmod {m_i}\)）。则方程的解为：\(x \equiv \sum\limits_{i=1}^n r_i t_i M_i \pmod M\)。
证明：对于第 \(i\) 个方程：
若 \(j \ne i\)，则 \(M_j\) 是 \(m_i\) 的倍数，即 \(M_j \equiv 0 \pmod {m_i}\)。
若 \(j = i\)，则 \(M_i t_i \equiv 1 \pmod {m_i}\)，即 \(r_i M_i t_i \equiv r_i \pmod {m_i}\)。
因此，\(\sum\limits_{i=1}^n r_i t_i M_i \equiv r_i \pmod {m_i}\)，确实是符合条件的解。
根据反证法可证没有其它解。\(\square\)
例题 2：CRT 的应用
[SDOI2010] 古代猪文 的一部分：\(f(x) \bmod p\) 容易求得（\(p\) 为质数），求 \(f(x) \bmod 999911658\) 的值。
注意到 \(999911658 = 2 \times 3 \times 4679 \times 35617\)，对四个质数分别求解，用 CRT 合并即可。
重要概念：扩展欧拉定理
【定理】扩展欧拉定理：
\[a^{\varphi(m)} \equiv a^{2\varphi(m)} \pmod m \]等价形式：
\[a^b \equiv \begin{cases} a^b & b < \varphi(m) \\ a^{b \bmod \varphi(m) + \varphi(m)} & b \ge \varphi(m) \end{cases} \pmod m \]证明：//TODO:
例题 3：幂塔
[Luogu P4139] 上帝与集合的正确用法：定义 \(a_0 = 1, a_n = 2^{a_{n-1}}\)。给定模数 \(m\)，可以证明，\(a_i \bmod m\) 在某一个 \(i\) 之后都是同一个值，求这个值。\(m \le 10^7\)。
注：我不喜欢 \(2^{2^{2^\cdots}} \bmod m\) 这种记法。非常有歧义。
只有永远扩展欧拉定理的第二种情况，才能保持同一个值。递归计算即可。因为 \(\varphi\) 的性质，递归只有 \(O(\log m)\) 层，可以通过。
重要概念：原根
【定义】原根：幂遍历了整个缩系的数。一般记为 \(g\)。
【定理】原根存在定理：\(m\) 有原根的充要条件为 \(m = 2, 4, p^\alpha, 2 p^\alpha\)。\(p\) 为奇质数，\(\alpha\) 为正整数。
证明：因为我不会证因为证明太长会打乱篇幅，所以见 OI Wiki。\(\square\)
如何计算原根？
【定理】原根判定定理：对于 \(x \perp m\)，\(x\) 是 \(m\) 的原根的充要条件是对于 \(\varphi(m)\) 的每个质因数 \(p\)，都有 \(x^{\frac {\varphi(m)} p} \not\equiv 1 \pmod m\)。
证明：若存在 \(d|\varphi(m)\) 使得 \(x^d \equiv 1\)，则 \(x\) 不是原根。
不难发现所有 \(\dfrac {\varphi(m)} p\) 覆盖了 \(\varphi(m)\) 的所有因数的倍数。\(\square\)
【定理】最小原根估计：对于质数 \(p\) 与任意 \(\varepsilon > 0\)，\(p\) 的最小原根是 \(O(p^{\frac 1 4 + \varepsilon})\) 级别。
证明：过于困难。
据 UOJ 群，合数 \(m\) 的最小原根还没有较好的估计。
从小到大枚举验证，即可得到一个数的最小原根。
[Luogu P6091]【模板】原根：求出一个数 \(m\) 的所有原根。
求出 \(m\) 的最小原根，记为 \(g\)。设还有一个原根为 \(g'\)，则 \(g' \equiv g^k\)。
\(g^k\) 是原根当且仅当 \(\gcd(k, \varphi(m)) = 1\)。
由此可得：
【定理】原根个数定理：若 \(m\) 有原根，则原根个数为 \(\varphi(\varphi(m))\)。
对数？
尝试定义 \(\log_a b\) 为 \(a^x \equiv b \pmod m\) 的解。不难发现 \(x\) 是一个在模 \(\varphi(m)\) 意义下的数。
但是容易发现解似乎不唯一。为了使得它唯一，有两种方案。
基于原根定义的对数
根据原根的知识，我们发现对于原根 \(g\)，可对于缩系中的元素 \(a\) 定义唯一的 \(\log_g a\)。
注：实际上一般使用的符号为 \(\text{ind}_g a\)。
性质
和普通的对数非常相似，性质很好。
\[\log_g (ab) \equiv \log_g a + \log_g b \pmod {\varphi(m)} \]\[\dfrac {\log_{g_1} a} {\log_{g_1} g_2} \equiv \log_{g_2} a \pmod {\varphi(m)} \]取最小值的对数
取 \(\log_a b\) 为 \(a^x \equiv b \pmod m\) 的最小解（不一定存在）。
如何计算对数？（BSGS 与 exBSGS）
BSGS
[TJOI2007] 可爱的质数：求 \(a^x \equiv b \pmod p\) 的最小解。\(p\) 为质数。
答案必定在 \(p-1\) 以内。
制定块长 \(t = \lceil \sqrt p \rceil\)。预处理所有的 \(a^{A \times t}\) 和 \(a^B\)，其中 \(0 \le A,B \le t\)。若有 \(a^{A \times t} \equiv b \times a^B\)（用哈希表实现），则答案为 \(A \times t - B\)。
exBSGS
[Luogu P4195]【模板】扩展 BSGS/exBSGS：求 \(a^x \equiv b \pmod m\) 的最小解。不保证 \(m\) 为质数。
见 P4195 题解 & 扩展 BSGS 学习笔记。这个做法非常优雅，而且似乎整个互联网上只有这一篇是这个做法。
平方根？（二次剩余）
【定义】二次剩余：对于 \(a \not\equiv 0\)，若存在 \(x\) 使得 \(x^2 \equiv a \pmod m\)，则 \(a\) 是模 \(m\) 的二次剩余，反之 \(a\) 是模 \(m\) 的非二次剩余。
注意：因为任意模数二次剩余并不常用，以下计算都在模奇质数 \(p\) 下进行。
【定理】欧拉判别法：若 \(a\) 是二次剩余，则 \(a^{\frac {p-1} 2} \equiv 1 \pmod p\)。反之，\(a^{\frac {p-1} 2} \equiv -1 \pmod p\)。
证明：
\[a^{p-1} - 1 \equiv 0 \pmod p \]\[(a^{\frac {p-1} 2} - 1) (a^{\frac {p-1} 2} + 1) \equiv 0 \pmod p \]所以 \(a^{\frac {p-1} 2}\) 等于 \(1\) 或 \(-1\)。
- 充分：若 \(a\) 是二次剩余，设 \(a \equiv b^2\)，则 \(a^{\frac {p-1} 2} \equiv b^{p-1} \equiv 1\)。
- 必要：若 \(a^{\frac {p-1} 2} \equiv 1\)，设 \(g\) 为一原根，则 \(a\) 可表示为 \(g^k\)，其中 \((p-1) | \dfrac {k(p-1)} 2\)，即 \(2|k\)，即 \(a\) 为二次剩余。
因此，\(a^{\frac {p-1} 2} \equiv 1\) 的充要条件是 \(a\) 为二次剩余。所以 \(a^{\frac {p-1} 2} \equiv -1\) 的充要条件是 \(a\) 为非二次剩余。\(\square\)
【定义】勒让德符号：\(\left( \dfrac a p \right) \equiv a^{\frac {p-1} 2} \equiv \begin{cases} 1 & a \text{ is a quadratic residue} \\ -1 & a \text{ is a quadratic nonresidue} \\ 0 & a \equiv 0 \end{cases} \pmod p\)。
复数
[Luogu P1962] 斐波那契数列：求 \(f_n \bmod m\) 的值，其中 \(f\) 是斐波那契数列，\(m = 10^9 + 7\)。
根据斐波那契数列通项公式：
\[f_n = \dfrac 1 {\sqrt 5} \left(\left(\dfrac {1 + \sqrt 5} 2\right)^n - \left(\dfrac {1 - \sqrt 5} 2\right)^n \right) \]如果 \(\sqrt 5 \bmod m\) 存在就可以直接计算了，但很可惜并没有。
定义一种新的复数 \(a + bi\)，其中 \(i^2 \equiv 5 \pmod m\)。即 \(i\) 为不存在的 \(\sqrt 5\)。这个技巧称为扩域。
用这种方式算出 \(\left(\left(\dfrac {1 + \sqrt 5} 2\right)^n - \left(\dfrac {1 - \sqrt 5} 2\right)^n \right)\) 的值（也是一个复数）。事实上，这个值的实部为 \(0\)，而虚部就是我们要求的答案。
如何计算（奇质数）二次剩余？（Cipolla）
//TODO:
参考资料
部分知识点参考《深入浅出程序设计竞赛 - 进阶篇》。
BSGS 与 exBSGS 与原根：
二次剩余：
扩域：
标签：意义,原根,pmod,dfrac,定理,varphi,数学,equiv From： https://www.cnblogs.com/AugustLight/p/-/Modular-Math