啥都不会。
最大公约数
辗转相除法（欧几里得算法）是更相减损术的优化，原理就是相减后最大公约数不会改变，过于显然，没必要设出来说明。
最小公倍数
容斥，两数之积除以两数的最大公约数。
tips：若数以质因数分解的形式给出，算最大公约数系数取 $\min$，算最小公倍数系数取 $\max$。
拓展欧几里得算法
求不定方程 $ax+by=\gcd(a,b)$ 的任意一个整数解。
令 $a\leq b,b>0$，假设我们当前已经求出了不定方程
$$b\bmod a\times x+ay=\gcd(b\bmod a,a)$$
的一组整数解 $x=x’,y=y’$，根据最大公约数的性质有
$$b\bmod a\times x’+ay’=\gcd(a,b)$$
把取模换掉
$$\left(b-\left\lfloor\frac{b}{a}\right\rfloor a\right)x’+ay’=\gcd(a,b)$$
整理成最初的形式
$$a\left(y’-\left\lfloor\frac{b}{a}\right\rfloor x’\right)+bx’=\gcd(a,b)$$
那么 $x=y’-\lfloor\frac{b}{a}\rfloor x’,y=x’$ 就是不定方程 $ax+by=\gcd(a,b)$ 的一组整数解。
递归求解的终止条件是 $a=0$，此时 $x=0,y=1$ 是一组解。在返回这组解的前提下，我们可以归纳出解的范围。
假设递归得到 $-b\bmod a\leq y’\leq b\bmod a,-a\leq x’\leq a$。
取 $y’=b\bmod a,x’=-a$ 有 $x\leq b\bmod a+b-b\bmod a=b,y\geq-a$。
取 $y’=-b\bmod a,x’=a$ 有 $x\geq-b\bmod a-b+b\bmod a=-b,y\leq a$。
容易发现递归最底层也就是 $\boldsymbol{a=0}$ 的情况比较特殊，假设是不可能成立的，但递归到上一层就一定成立了。所以当 $a>0$ 时 exgcd 求出的不定方程 $ax+by=\gcd(a,b)$ 的解 $x,y$ 满足 $x\in[-b,b],y\in[-a,a]$。
欧拉函数
$\phi(n)$ 表示小于等于 $n$ 的与 $n$ 互质的数的个数，所以 $\phi(1)=1$。
当 $n$ 为质数时，$\phi(n)=n-1$。
求单个数的欧拉函数
由唯一分解定理，设 $n=\Pi_{i=1}^s p_i^{k_i}$。然后对于质因子容斥，可以发现容斥式就是 $n\Pi_{i=1}^s\frac{p_i-1}{p_i}$ 的展开式。
在分解质因数的时候直接计算即可。
费马小定理
设 $a,p\in\mathbb{N^+}$，$p$ 是质数，且满足 $\gcd(a,p)=1$，则有 $a^{p-1}\equiv 1\pmod p$。
引理 1
对于任意三个正整数 $a,b,c$ 满足 $\gcd(c,m)=1$，若 $ac\equiv bc\pmod m$，则 $a\equiv b\pmod m$。
移项变成 $c(a-b)\equiv 0\pmod m$ 后，因为互质所以只能是 $a-b\equiv 0\pmod m$。
引理 2
若 $\{a_1,\cdots,a_m\}$ 是模 $m$ 的一个完全剩余系，整数 $b$ 满足 $\gcd(b,m)=1$，那么 $\{a_1b,\cdots,a_mb\}$ 也是模 $m$ 的一个完全剩余系。
反证，如果存在 $a_ib\equiv a_jb\pmod m$，根据引理 1 可得 $a_i\equiv a_j\pmod m$，不符合完全剩余系的定义。
证明
构造模 $p$ 的一个完全剩余系 $\{0,1,2,\cdots,p-1\}$。
根据引理 2 可得 $\{0,a,2a,\cdots,(p-1)a\}$ 也是模 $p$ 的一个完全剩余系。
一一对应可得 $1\times 2\times 3\times\cdots\times(p-1)\equiv a\times 2a\times\cdots\times(p-1)a\pmod p$。
即 $(p-1)!\equiv(p-1)!\times a^{p-1}\pmod p$。
显然 $\gcd(p,(p-1)!)=1$，根据引理 1 即可证毕。
欧拉定理
设 $a,n\in\mathbb{N^+}$ 且满足 $\gcd(a,n)$，则有 $a^{\phi(n)}\equiv 1\pmod n$。
容易看出费马小定理其实是欧拉定理的特殊情况。
首先两个与 $n$ 互质的数的乘积仍然与 $n$ 互质。
所以把费马小定理证明里面的完全剩余系换成与 $n$ 互质的剩余系即可。
乘法逆元
乘法逆元，是指数学领域群 $G$ 中任意一个元素 $a$，都在 $G$ 中有唯一的逆元 $a’$，具有性质 $a\times a’=a’\times a=e$，其中 $e$ 为该群的单位元。
单位元是集合里的一种特别的元，与该集合里的运算有关。当它和其他元素结合时，并不会改变那些元素。
所以在模域下的乘法中，单位元就是 $1$。
具体地，若 $a\times b\equiv 1\pmod p$，则称 $b$ 是 $a$ 在模 $p$ 意义下的乘法逆元，记作 $a^{-1}$，即 $b\equiv\frac{1}{a}\pmod p$。
可以写成 $a\times b+p\times q=1$ 的形式，根据裴蜀定理只有 $a$ 与 $p$ 互质时才有解，这也就是乘法逆元存在的条件。
在求 $\frac{y}{x}$ 时我们可以先求出 $\frac{1}{x}$ 再乘上 $y$。
费马小定理求单个数的乘法逆元
只能解决 $p$ 是质数的情况。
$$a\times b\equiv 1\pmod p$$
$$a\times b\equiv a^{p-1}\pmod p$$
$$b\equiv a^{p-2}\pmod p$$
欧拉定理求单个数的乘法逆元
需要事先求出 $\phi(a)$。
$$a\times b\equiv 1\pmod p$$
$$a\times b\equiv a^{\phi(a)}\pmod p$$
$$b\equiv a^{\phi(a)-1}\pmod p$$
前缀积求一堆数的乘法逆元
在求组合数时我们常常会需要求阶乘的逆元。
先用上面的方法求出 $n!$ 的逆元，然后考虑倒着递推，从 $i$ 推到 $i-1$：
$$\frac{1}{(i-1)!}\equiv\frac{1}{i!}\times i\pmod p$$
再深入思考一下你会发现：
$$\frac{1}{i!}\times(i-1)!\equiv\frac{1}{i}\pmod p$$
这样就做到了线性求 $1\sim n$ 的逆元。
最后将 $i$ 替换成 $a_i$ 就行了。
威尔逊定理
$>1$ 的整数 $p$ 满足 $(p-1)!\equiv-1\pmod p$ 的充分必要条件是 $p$ 为质数。
充分性
两边同除以 $p-1$ 得到 $(p-2)!\equiv 1\pmod p$。
考虑逆元为其本身的数，可以发现只有 $1$ 和 $p-1$。
所以 $2\sim p-2$ 的逆元组成的集合同样为 $2\sim p-2$，可以两两划分成乘积为 $1$ 的组。
必要性
如果 $p$ 不为质数，那么可以将 $p$ 表示成 $a\times b(1<a,b<p)$。
当 $a=b$ 时，发现 $p=4$ 符合，$p\geq 9$ 时 $a<2a<p-1$。
那么除了 $p=4$ 以外 $(p-1)!$ 一定存在因子 $p$，所以 $(p-1)!\equiv 0\pmod p$。