欧拉函数

在 $[1,n]$ 中，只有 $p$ 的倍数不与 $n=p^k$ 互质.

$∵\;[1,n]$ 中 $p$ 的倍数有 $\dfrac{n}{p}=\dfrac{p^k}{p}=p^{k-1}$ 个，

$∴\varphi(n)=n-p^{k-1}=p^k-p^{k-1}$.

若 $n$ 有质因子 $p$，则 $p$ 的倍数不与 $n$ 互质.

$[1,n]$ 中 $p$ 的倍数有 $\cfrac{n}{p}$ 个，则剩下的 $n-\cfrac{n}{p}=n\cdot(1-\cfrac{1}{p})$ 个数不是 $p$ 的倍数. 也就是说，这 $n$ 个数中，非 $p$ 的倍数占比为 $1-\cfrac{1}{p}$.

根据定义，$[1,n]$ 中有 $\varphi(n)$ 个数不是 $p_1∼p_m$ 的倍数（即与 $n$ 互质）. 由乘法原理得：

$$\varphi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_m})=n\prod_{i=1}^{m}(1-\frac{1}{p_i})$$

设 $n$ 有 $x$ 个质因子 $p_1\sim p_x$，

设 $m$ 有 $y$ 个质因子 $q_1\sim q_y$，

$∵n,m$ 互质，$∴n,m$ 的质因子互不相同.

$∴nm$ 有 $x+y$ 个质因子 $p_1\sim p_x,q_1\sim q_y$.

由 $\varphi$ 函数的通项公式可得：

$$\begin{aligned} \varphi(n)\cdot \varphi(m)&=(n\prod_{i=1}^{x}(1-\frac{1}{p_i}))\cdot (m\prod_{i=1}^{y}(1-\frac{1}{q_i}))\\ &=nm\prod_{i=1}^{x}(1-\frac{1}{p_i})\prod_{i=1}^{y}(1-\frac{1}{q_i})\\ &=\varphi(nm) \end{aligned}$$

即证.

设 $C=\{C_1,C_2,\cdots,C_{\varphi(n)}\}$ 为模 $n$ 的 简化剩余系.

设 $aC=\{aC_1,aC_2,\cdots,aC_{\varphi(n)}\}$，即 $C$ 中的每个元素乘 $a$.

引理 1

由 剩余系 的定义得：

$$C_i\not≡C_j \ (\bmod \ n)(i\not=j)$$

$∵a,n$ 互质，由同余的 同乘性 可知：

$$aC_i\not≡aC_j \ (\bmod \ n)(i\not=j)$$

$∴aC$ 为模 $n$ 的剩余系.

引理 2

$∵a,n$ 互质，根据 欧几里得算法 有：

$$gcd(a,n)=gcd(n,a \bmod n)=1$$

$∴a \bmod n$ 也与 $n$ 互质. 根据 简化剩余系 的定义可知：

$$a \bmod n\in C$$

$∵\;$简化剩余系满足 乘法封闭 性质，所以：

$$\begin{cases} a \bmod n\in C \\ C_i\in C \end{cases} \eq(a \bmod n)\cdot C_i \bmod n\in C \eq aC_i \bmod n\in C$$

$∴aC_i \bmod n$ 与 $n$ 互质，即 $aC$ 中的任意元素模 $n$ 后与 $n$ 互质.

结合引理 $1$、引理 $2$ 可知 $aC$ 也为 $n$ 的简化剩余系.

显然，$C$ 的所有元素之积和 $aC$ 的所有元素之积模 $n$ 同余，即：

$$\prod_{i=1}^{\varphi(n)}C_i≡\prod_{i=1}^{\varphi(n)}aC_i \ (\bmod \ n)$$

$$\prod_{i=1}^{\varphi(n)}C_i≡a^{\varphi(n)}\cdot \prod_{i=1}^{\varphi(n)}C_i \ (\bmod \ n)$$

$$(a^{\varphi(n)}-1)\prod_{i=1}^{\varphi(n)}C_i≡0 \ (\bmod \ n)$$

$∵C$ 中的所有元素模 $n$ 后与 $n$ 互质，所以：

$$\prod_{i=1}^{\varphi(n)}C_i\not≡0 \ (\bmod \ n)$$

$∴a^{\varphi(n)}-1≡0\pmod{n}$，即 $a^{\varphi(n)}≡1\pmod{n}$.

当 $p\mid a$ 时，费马小定理显然成立，故只需讨论 $p\nmid a$ 的情况.

当 $p\nmid a$ 时，$∵p$ 是质数 $∴a,p$ 没有公因数（即 $a,p$ 互质）. 根据 欧拉定理 有：

$$a^{ \varphi(p)}≡1 \ (\bmod \ p)$$

$∵p$ 为质数，由 性质 可知 $\varphi(p)=p-1$. 代入上式：

$$a^{ p-1}≡1 \ (\bmod \ p)$$

即证.

设 $b \bmod \varphi(n)=q$，则 $b$ 可以表示为 $k\cdot \varphi(n)+q$. 代入 $a^b$ 得：

$$a^b=a^{k\cdot \varphi(n)+q}=\big(a^{\varphi(n)}\big)^k\cdot a^q$$

根据 欧拉定理，当 $a,n$ 互质时，有：

$$a^{\varphi(n)}≡1 \ (\bmod \ n)$$

由同余的 同幂性、 同乘性 可知：

$$\big(a^{\varphi(n)}\big)^k≡1^k=1 \ (\bmod \ n)$$

$$\big(a^{\varphi(n)}\big)^k\cdot a^q≡a^q \ (\bmod \ n)$$

$$a^b≡a^q \ (\bmod \ n)$$

即 $a^b≡a^{b \bmod \varphi(n)}\pmod{n}$.