课程目录
本页目录

§3.3

欧拉函数 φ(n)\varphi(n)

1 到 n 之间,与 n 互质的数有多少个。

第三章 数论函数 更新 2026.06.08 13 min 数论 / 数论函数

定义

表示 中与 互质的正整数个数,即

约定 。

基本性质

(a) 素数

若 是素数,则

因为 中除了 自身,其余 个数都与 互质。

(b) 素数幂

若 是素数,则

因为 中与 不互质的数恰好是 的倍数,共有 个。

计算公式

设 为标准分解,则

证明(容斥原理):在 中,先去掉所有 的倍数,再去掉所有 的倍数,再把被重复去掉的 的倍数加回来。依此类推,得到

最后一步用了展开式 。


定理 1

对任意 ,有

思路

考虑集合

则 。对每个 ,令

则 。只需证明 构成 的一个划分。

证明

(1)两两不交。 设 且 。若存在 ,则

且 。由 得 ;又因为 ,所以 。同理 ,于是 ,矛盾。因此 。

(2)并集包含于 。 任取 ,存在 使 ,其中 且 。由 ,

且 ,故 。

(3) 包含于并集。 任取 ,写 ,其中 。令 ,则

故 。因此 。

综上,,于是


引理

设 。若 遍历 的全部因子, 遍历 的全部因子,则 遍历 的全部因子。

证明

第一步:。 由 、,立即得到 。

第二步:表示唯一。 证明 当且仅当 、。

假设 且 。由

以及 ,可得 。于是 ;同理 ,故 ,进而 ,与假设矛盾。

第三步:遍历全部因子。 任取 ,令

则 。又

且 ,所以 。因此每个 都能写成 的形式。

结合三步,引理得证。


积性(定理 2)

若 ,则

法一:直接展开

设 ,。由 知 与 不相交。于是

法二:数学归纳

当 时结论显然。假设结论对所有小于 的正整数成立。由定理 1,

因为 ,所以 ,从而 。于是

最后一步再次使用定理 1。因此 。

推论:由积性,


定理 3

设 ,则

若 ,则 。

证明

(1) 令 。则

(2) 设 ,并令 。由(1),

其中最后一步约去了 的因子。将 按素因子拆开:

右边是整数,故 。