欧拉函数

欧拉函数 $\varphi(n)$ 统计与 $n$ 互素的数的个数，是简化剩余系的核心量。

定义

对正整数 $n$，$\varphi(n)$ 为 $1,2,\dots,n$ 中与 $n$ 互素的整数个数：

$$\varphi(n) = \#\{k : 1\le k\le n,\ \gcd(k,n)=1\}$$

性质

• $p$ 为素数时 $\varphi(p) = p-1$，且 $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$
• 积性：$\gcd(m,n) = 1 \Rightarrow \varphi(mn) = \varphi(m)\varphi(n)$
• 一般公式：设 $n = \prod_{i=1}^{r} p_i^{\alpha_i}$，则

$$\varphi(n) = n\prod_{i=1}^{r}\left(1 - \frac{1}{p_i}\right)$$

• $\displaystyle\sum_{d\mid n}\varphi(d) = n$

欧拉定理与费马小定理

若 $\gcd(a,n) = 1$，则

$$a^{\varphi(n)} \equiv 1 \pmod n$$

当 $n = p$ 为素数时退化为费马小定理：若 $p\nmid a$，则 $a^{p-1} \equiv 1 \pmod p$。

示例

• $\varphi(12) = \#\{1,5,7,11\} = 4$
• $\varphi(100) = 100\cdot\left(1 - \frac12\right)\left(1 - \frac15\right) = 40$
• 由欧拉定理 $7^{\varphi(10)} = 7^4 \equiv 1 \pmod{10}$，故 $7^{4k} \equiv 1 \pmod{10}$