【数学】简化剩余系、欧拉函数、欧拉定理与扩展欧拉定理

简化剩余系

与完全剩余系略有区别。
我们定义数组 $a_i(1\le i\le n)$ 为模 $m$ 的简化剩余系，当且仅当 $\forall 1\le i,j\le n$，有 $a_i\not\equiv a_j(\mathrm{mod}m)$，$\forall 1\le i\le n$，有 $\gcd (m,a_i)=1$

1. 若 $a_i(1\le i\le n)$ 为模 $m$ 的简化剩余系，$\gcd (b,m)=1$，则 $b\cdot a_i(1\le i\le n)$ 也为模 $m$ 的简化剩余系。

简化剩余系的性质都在欧拉函数上了。。。

欧拉函数

定义欧拉函数 $\phi (n)$ 为小于等于 $n$ 且与 $n$ 互质的数的个数，即模 $n$ 的简化剩余系的大小。

性质

1. $\phi (n)=n\prod _{\begin{array}{l}p\in \text{prime}\\ p|n\end{array}}(1-\frac{1}{p})$
2. 若 $\gcd (n,m)=1$，则 $\phi (nm)=\phi (n)\phi (m)$，即 $\phi (n)$ 为积性函数

欧拉定理

若 $\gcd (a,n)=1$，则$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$
构造 $b_i(1\le i\le \phi (n))$ 为模 $n$ 的简化剩余系，则 $c_i=b_i\cdot a(1\le i\le \phi (n))$ 也为模 $n$ 的简化剩余系
则 $\prod _{i=1}^{\phi (n)}{c}_i\equiv \prod _{i=1}^{\phi (n)}{b}_i(\mathrm{mod}n)$
即 $\prod _{i=1}^{\phi (n)}{b}_i\cdot a\equiv \prod _{i=1}^{\phi (n)}{b}_i(\mathrm{mod}n)$
约去 $\prod _{i=1}^{\phi (n)}{b}_i$，得 $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$，证毕。

扩展欧拉定理

由欧拉定理，得到扩展欧拉定理：$a^n\equiv a^{n\text{mod}\phi (n)+\phi (n)}(\mathrm{mod}n)$

代码（就是快速幂，不贴了）

习题

• 洛谷P5091