欧拉函数

Abstract

欧拉函数（Euler's Totient Function） $ϕ (n)$ 表示不超过 $n$ 且与 $n$ 互素的正整数个数。利用容斥原理可以推导出其乘积公式 $ϕ (n) = n \prod_{p ∣ n} (1 - 1/ p)$ ，该函数在数论和密码学中有核心地位，是费马小定理到欧拉定理的推广基础。

定义

欧拉函数（Euler's Totient Function）

设 $n$ 为正整数，欧拉函数 $ϕ (n)$ 定义为不超过 $n$ 且与 $n$ 互素的正整数个数： $ϕ (n) = ∣ {k \in Z^{+} : 1 \leq k \leq n, g cd (k, n) = 1} ∣$

欧拉函数的乘积公式

设 $n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}$ 为 $n$ 的素因子分解，则 $ϕ (n) = n (1 - \frac{1}{p _{1}}) (1 - \frac{1}{p _{2}}) \dots (1 - \frac{1}{p _{k}}) = n \prod_{p ∣ n} (1 - \frac{1}{p})$

欧拉定理

若 $g cd (a, n) = 1$ ，则 $a^{ϕ (n)} \equiv 1 (mod n)$ 。

当 $n$ 为素数 $p$ 时， $ϕ (p) = p - 1$ ，欧拉定理退化为费马小定理： $a^{p - 1} \equiv 1 (mod p)$ 。

核心性质

编号	性质	公式 / 说明
P1	乘积公式	$ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p})$ ， $p$ 遍历 $n$ 的所有不同素因子
P2	素数的欧拉函数	若 $p$ 为素数，则 $ϕ (p) = p - 1$
P3	素数幂	$ϕ (p^{k}) = p^{k} - p^{k - 1} = p^{k} (1 - 1/ p)$
P4	积性函数	若 $g cd (m, n) = 1$ ，则 $ϕ (mn) = ϕ (m) ϕ (n)$
P5	两素数乘积	$ϕ (pq) = (p - 1) (q - 1)$ （ $p, q$ 为不同素数）
P6	与费马小定理的关系	欧拉定理 $a^{ϕ (n)} \equiv 1 (mod n)$ 是费马小定理的推广
P7	求和恒等式	$d ∣ n \sum ϕ (d) = n$ （对所有正因子 $d$ 求和）

关系网络

graph LR
    A[欧拉函数]
    B[容斥原理]
    C[素数]
    D[整除]
    E[最大公约数]
    F[费马小定理]

    A -- "容斥原理推导乘积公式" --> B
    A -- "素数 p 的 φ=p-1" --> C
    A -- "基于整除性定义性质" --> D
    A -- "gcd=1 的判定" --> E
    A -- "推广为欧拉定理" --> F
    F -- "φ=p-1 时退化" --> A
    C -- "素因子分解" --> A

章节扩展

容斥原理：欧拉函数的乘积公式可通过容斥原理的补集形式严格推导
素数：素数的欧拉函数值 $ϕ (p) = p - 1$ 是最简单的特殊情况
整除：欧拉函数的定义依赖于整除性和素因子分解
最大公约数： $ϕ (n)$ 的定义核心是 $g cd (k, n) = 1$ ，与最大公约数直接相关
费马小定理：费马小定理是欧拉定理（ $a^{ϕ (n)} \equiv 1 (mod n)$ ）在 $n$ 为素数时的特例

补充

容斥原理推导乘积公式

设 $n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}$ 为 $n$ 的素因子分解。定义性质 $P_{i}$ 为”整数能被 $p_{i}$ 整除”（ $i = 1, 2, \dots, k$ ）。不超过 $n$ 且能被 $p_{i_{1}} p_{i_{2}} \dots p_{i_{m}}$ 整除的整数有 $\frac{n}{p _{i_{1}} p _{i_{2}} \dots p _{i_{m}}}$ 个（因为 $n$ 是这些素数的幂的乘积，所以整除结果为整数）。

由容斥原理的补集形式： $ϕ (n) = n - \sum_{i} \frac{n}{p _{i}} + \sum_{i < j} \frac{n}{p _{i} p _{j}} - \sum_{i < j < l} \frac{n}{p _{i} p _{j} p _{l}} + \dots + (- 1)^{k} \frac{n}{p _{1} p _{2} \dots p _{k}}$

因式分解即得乘积公式： $ϕ (n) = n (1 - \frac{1}{p _{1}}) (1 - \frac{1}{p _{2}}) \dots (1 - \frac{1}{p _{k}}) = n \prod_{p ∣ n} (1 - \frac{1}{p})$

计算示例

$ϕ (12) = ϕ (2^{2} \cdot 3) = 12 (1 - \frac{1}{2}) (1 - \frac{1}{3}) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} = 4$

验证：不超过12且与12互素的正整数为 1, 5, 7, 11，共4个。

$ϕ (30) = ϕ (2 \cdot 3 \cdot 5) = 30 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 8$

验证：1, 7, 11, 13, 17, 19, 23, 29，共8个。

$ϕ (pq)$ （ $p, q$ 为不同素数） $= pq (1 - \frac{1}{p}) (1 - \frac{1}{q}) = (p - 1) (q - 1)$

RSA 密码系统中的应用

欧拉函数是 RSA 公钥密码系统的数学基础。在 RSA 中，选取两个大素数 $p$ 和 $q$ ，计算 $n = pq$ 和 $ϕ (n) = (p - 1) (q - 1)$ 。公钥 $e$ 和私钥 $d$ 满足 $e d \equiv 1 (mod ϕ (n))$ ，从而保证加密解密的正确性。 $ϕ (n)$ 的难计算性（需要知道 $n$ 的素因子分解）是 RSA 安全性的基础。

参见

容斥原理：欧拉函数乘积公式的推导工具
素数：素数的欧拉函数值及素因子分解
整除：欧拉函数定义的基础——整除性与素因子
最大公约数： $g cd (k, n) = 1$ 的判定
费马小定理：欧拉定理在素数模下的特例

CS Wiki

探索

欧拉函数

欧拉函数

定义

核心性质

关系网络

章节扩展

补充

参见

关系图谱

目录

反向链接