同余关系
定义
数学中同余关系是一种等价关系。当两个整数a, b除以同一个正整数n，若得到相同的余数，则这两个整数同余。记做\(a\equiv b\ \ \pmod n\).
性质
整除性：a，b相减能被n整除
传递性：等价关系的共有特性
\(\left.\begin{array}{l} a \equiv b(\bmod m) \\ b \equiv c(\bmod m) \end{array}\right\} \Rightarrow a \equiv c \quad(\bmod m)\)
保持基本运算：(加减乘)
\(\left.{\begin{matrix}a\equiv b{\pmod {m} }\\ c\equiv d{\pmod {m} }\end{matrix} }\right\}\Rightarrow \left\{ {\begin{matrix}a\pm c\equiv b\pm d{\pmod {m} }\\ ac\equiv bd{\pmod {m} }\end{matrix} }\right.\)
可进一步写成：
\(a\equiv b{\pmod {m} }\Rightarrow {\begin{cases}an\equiv bn{\pmod {m} },\forall n\in \mathbb {Z} \\ a^{n}\equiv b^{n}{\pmod {m} },\forall n\in \mathbb {N} ^{0}\end{cases} }\)
放大缩小底数：（对底数加减模数的倍数均可）
k为整数，n为正整数，\((km\pm a)^{n}\equiv (\pm a)^{n}{\pmod m}\)
放大缩小模数：（对模数和等式两边的数同乘k）
\(k\)为正整数，\(a\equiv b{\pmod m}\)，当且仅当\(ka\equiv kb\pmod {km}\)
还有几个性质，懒得码了，详见wiki：同余
欧拉函数
对正整数\(n\)，欧拉函数\(\varphi(n)\)为小于等于\(n\)的正整数中，与\(n\)互质的数的个数。
欧拉定理
若\(n,a\)为正整数，且\(n, a\)互素(即\(gcd(n, a) = 1\)) ，则$a^{(n)} $.
一般的证明中会用到“所有与 $ n $互质的同余类构成一个群”的性质，也就是说，设 \(\left\{ {\overline {a_{1} }},{\overline {a_{2} }},\cdots ,{\overline {a_{\varphi (n)} }}\right\}\)是比 $ n $ 小的正整数中所有与\(n\)互素的数对应的同余类组成的集合（这个集合也称为模\(n\)的简化剩余系）。这些同余类构成一个群，称为整数模n乘法群。因为此群阶为\(\varphi (n)\)，所以 $ a^{(n)} $。(开始后悔近世代数没认真学)
费马小定理
当n为素数的时候,，则\(\varphi(n)=n-1\)，即\(a^{n-1}\equiv1\ \ \pmod n\).
模逆元
一整数a对同余n的模逆元是指满足\(ab\equiv1\ \pmod n\)的整数 b。
整数 a 对模数 n 之模逆元存在的充分必要条件是 a 和 n 互素
如何求a 对模数 n 之模逆元？
由于a与n互质，所以可用欧拉定理，即\(a^{\varphi(n)}=a\cdot a^{\varphi(n)-1}\equiv1\ \ \pmod n\)，即a对模数n的模逆元是\(a^{\varphi(n)-1}\)。
特别的，当n为质数时，根据费马小定理，a对模数n的模逆元是\(a^{n-2}\)。(这样就可使用快速幂在\(log(n)\)时间求出a的逆元)
还有个小trick:
求X的模MOD逆元时，若\(X\ \big|\ (MOD +1)\)，则X的模逆元可表示成\(\frac{MOD + 1} X\)。比如当MOD为奇数时，2的逆元是\(\frac {MOD +1}2\)