初等数论（提高组）
题单介绍
[数论](https://rosmarinus.blog.luogu.org/rosmarinus-ji-miao-shuo-lun-xue-xi-bi-ji)
1. 同余
给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。
2. 欧拉定理与欧拉函数
如果正整数 n 和整数 a 互质，那么就有
$a^{\phi(n)}\equiv 1 (mod\ n)$
其中欧拉函数 $\phi(n)$ 是「小于 n 的正整数中和 n 互质的数」的个数
3. 费马小定理
为欧拉定理的特殊形式，若n为质数，那么就有$a^{n-1}\equiv 1 (mod\ n)$
4. 威尔逊定理
p 为质数 $\iff (p-1)! \equiv -1 (mod\ p)$
5. 裴蜀定理
设a、b是不全为零的整数，则存在整数x、y , 使得$ax+by=gcd(a,b)$ .
6. [逆元](https://www.luogu.com.cn/blog/zyxxs/post-xiao-yi-jiang-tan-qian-tan-sheng-fa-ni-yuan)
一般指乘法逆元。如果一个线性同余方程 $ax\equiv 1(mod\ b)$，则$x$称为$a\ mod\ b$的逆元，记作 $a^{-1}$。
一般可使用裴蜀定理（扩展欧几里得算法）或欧拉定理（快速幂算法）算出逆元。
7. 扩展欧几里得算法
```cpp
void exgcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1, y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= a / b * x;
}
```
8. [中国剩余定理](https://oi-wiki.org/math/number-theory/crt/)
9. [欧拉函数与欧拉定理](https://www.luogu.com.cn/blog/Morning-Glory/ou-la-ji-lie-yang-xi-zheng-ming-post)
[题单1](https://www.luogu.com.cn/training/200296)
[题单2](https://www.luogu.com.cn/training/3135)
[题单3（exgcd）](https://www.luogu.com.cn/training/75320)
[题单4（欧拉定理）](https://www.luogu.com.cn/training/7052)