逆定理

\forall a,b\in \Z，若d>0 且d 为a,b 的公因数，且存在x,y，使得ax+by=d，则：

乘法逆元

若存在ax\equiv 1\pmod p，则称x 为a 关于p 的逆元，记x=a^{-1}。

当\gcd(a,p)=1 的时候（ p 为质数）逆元一定存在。

费马小定理

对于质数p，若\gcd(a,p)=1，满足a^{p-1}\equiv 1\pmod p，a^{p-2}\equiv a^{-1}\pmod p。

常用于分数取模，即：

详见[这里](https://www.cnblogs.com/TH911/p/-/Fermat-Little-Therorem)

欧拉定理

令n=p_1^{c_1}p_2^{c_2}p_3^{c_3}\cdots p_k^{c_k}，满足p_i 为质数 $ c_i 0 $。

令n=p_1^{c_1}p_2^{c_2}p_3^{c_3}\cdots p_k^{c_k}，满足p_i 为质数 $ c_i>0 $。

则：

$$

\varphi(n)=n\left(1-\frac 1{p_1}\right)\left(1-\frac 1{p_2}\right)\left(1-\frac 1{p_3}\right)\cdots\left(1-\frac 1{p_k}\right)

$$

推导见[容斥原理求解欧拉函数](https://www.cnblogs.com/TH911/p/-/Combinatorics#求解欧拉函数-varphin)。（组合数学没搬，放的原 Blog 链接）

:::

若\gcd(a,p)=1，则a^{\varphi(p)}\equiv1\pmod p。

显然，当p 为质数时，有\varphi(p)=p-1，即费马小定理。因此，**费马小定理为欧拉定理的特殊形式**。

## 扩展欧拉定理

对于任意的a,p,b\in \N^*，若满足\gcd(a,p)>1,b\geq \varphi(p)，有：

$$

a^b\equiv a^{b\bmod \varphi(p)+\varphi(p)}\pmod p

$$

当\gcd(a,p)=1 时即欧拉定理。

可以使用初等证明或群论证明。

常用于降幂。

## 扩展欧几里得算法 exgcd

注意不是“类欧几里得算法”。

用于求关于x,y 的不定方程ax+by=\gcd(a,b) 的**一组整数特解**。

不妨令a>b。

考虑到a=\left\lfloor\dfrac{a}{b}\right\rfloor b+a\bmod b，代入可得：

$$

\left(\left\lfloor\frac{a}{b}\right\rfloor b+a\bmod b\right)x+by=\gcd(a,b)

$$

因此：

$$

令a'=b,x'=\left\lfloor\dfrac ab\right\rfloor x+y,b'=a\bmod b,y'=x，有：

$$

a'x'+b'y'=\gcd(a',b')

$$

显然，可以**递归求解**。

那么直到b=0 时，可以直接解得一组整数特解\begin{cases}x=1\\y=0\end{cases}。

设最终递归出来的解为\begin{cases}x=x_0\\y=y_0\end{cases}。

令\Delta b=\left\vert\dfrac{b}{\gcd(a,b)}\right\vert，\Delta a=\left\vert\dfrac a{\gcd(a,b)}\right\vert，则对于\forall k\in \N^*，方程存在一组解为\begin{cases}x=x_0+k\Delta b\\y=y_0-k\Delta a\end{cases}。

### exgcd 与同余方程

exgcd 求解的是不定方程：

$$

ax+by=\gcd(a,b)

$$

而同余方程形如：

$$

ax\equiv c\pmod b

$$

可以将同余方程转化为：

$$

ax+by=c

$$

进而使用 exgcd 求解