$$\huge 同余$$

$同余定义$

$若整数a,b满足a\ mod\ p = b \ mod\ p$

$那么就称a,b在模p意义下同余,记为a \equiv b(mod \ p)$

$同余方程$

$形如ax = b (mod \ p)这样的方程被称为同余方程$

$欧拉定理$

$若a,n互质,那么a^{\varphi (n)} \equiv 1 (mod\ n)$

$其中\varphi (n)表示$欧拉函数

$费马小定理$

$根据欧拉定理,对于任意整数,a^n \equiv a(mod \ n)$

$乘法逆元$

$给定一个数a,求a^{-1}模b意义下的值$

扩展欧几里得算法

$设x \equiv a^{-1}(mop \ b)$

$那么 ax \equiv 1 (mod \ b)$

$因为同余,所以ax + by = 1 (y可能为负数)$

$也就是用$扩展欧几里得算法$求x的最小解$

快速幂

$若模数b为质数,那么通过费马小定理$

$$a^b \equiv a (mod \ b)$$

$$a^{b - 2} \equiv a^{-1} (mod b)$$

$通过快速幂可以快速求出a^{b-2}模b的结果,即a的逆元$

$解同余方程$

$$ax \equiv c (mod \ b)$$

$$ax + by = c$$

$用扩展欧几里得算法就可以求解$