同余

同余（英语：Congruence modulo，符号：≡）在数学中是指数论中的一种等价关系。当两个整数除以同一个正整数，若得相同余数，则二整数同余。同余是抽象代数中的同余关系的原型。最先引用同余的概念与“≡”符号者为德国数学家高斯。

$a\equiv b\mod m$

整除性

$a\equiv b\mod m\Rightarrow m|(a-b)$

即是说 a 和 b 之差是 m 的倍数

同余可以用来检验一个数是否可以整除另外一个数，见整除规则。

传递性

保持基本运算

保持：加、减、乘、乘方

不行：除法、开方

乘法逆元

除法的解决方案

费马小定理求乘法逆元：

费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有

$a^{p-1}≡1\mod p$

则有：

$a^{-1}≡a^{p-2}\mod p$

常见的大质数：

1e9+7, 1e9+9