同余式
若两个整数 \(a, b\) 模 \(m\) 的余数相同，则称 \(a, b\) 模 \(m\) 同余，记为 \(a \equiv b \pmod{m}\)。
费马小定理
若 \(p\) 为质数，且 \(a, p\) 互质，则 \(a^{p-1} \equiv 1 \pmod{p}\)。
欧拉定理
若 \(a, m\) 互质，则 \(a^{\varphi(m)} \equiv 1 \pmod{p}\)，其中 \(\varphi(\cdot)\) 为欧拉函数。
扩展欧拉定理
扩展欧拉定理(欧拉降幂公式)如下：
\[a^b \equiv \begin{cases} a^{b\mod{\varphi(m)}},&\gcd(a,m)=1\\ a^{b},&\gcd(a,m)\ne1,b<\varphi(m), &\pmod{m}\\ a^{b\mod{\varphi(m)}\ +\ \varphi(m)},&\gcd(a,m)\ne1, b\ge\varphi(m)\\ \end{cases} \]无 \(a, m\) 互质条件。
威尔逊定理
任意一个大于 \(1\) 的数 \(p\) 是素数的充要条件为：
\(p>1, (p-1)!\equiv -1 \pmod{p} \Leftrightarrow p\in\mathbb{P}\)
推论
- 若 \(p\) 是素数，则\((p-1)!+1 \equiv 0 \pmod{p}\)
- 若 \(p\) 是大于 \(4\) 的合数，则 \((p-1)!\equiv 0\pmod{p}\)
乘法逆元
若 \(a, b\) 互质，且满足同余方程 \(ax \equiv 1 \pmod{b}\)，则称 \(x\) 为 \(a\) 模 \(b\) 的乘法逆元，记作 \(a^{-1}\)