企业官网建设流程全解析

1. 从一道手算题说起：欧拉函数为什么值得单独拆一遍

第一次认真对待欧拉函数，是在算 φ(360) 这种看着人畜无害的题目上。360 = 2³·3²·5，按标准分解式套公式，φ(360) = 360×(1-1/2)×(1-1/3)×(1-1/5) = 96。答案是对的，但当时我心里其实并不踏实：那个连乘积凭什么是这样？为什么拆成素数幂就能乘起来，拆成两个互素的合数也能乘起来？这条“积性”的性质，是欧拉函数所有计算技巧的地基，也是初等数论里最容易被当成“显然”糊弄过去的一步。

这篇内容就专门聊欧拉函数积性的证明。它不是一道题，而是一个证明样板：怎样把一个“计数”问题，转化成“结构”问题；怎样用剩余系的乘法性质，把一个二维的筛选过程拆成两个一维的筛选过程。适合正在啃初等数论、准备竞赛、或者写程序需要用到欧拉函数的人看。哪怕你只会辗转相除，也能顺着往下读，因为所有关键步骤我都会把“为什么这么想”交代清楚。

先把结论摆出来：若 gcd(m, n) = 1，则 φ(mn) = φ(m)·φ(n)。这个结论叫积性，注意它不叫完全积性，条件 gcd(m, n) = 1 是硬性门槛，丢掉它结论立刻崩。φ(4) = 2，φ(2) = 1，φ(8) = 4，而 2×1 = 2 ≠ 4，这就是反例。很多人背公式背得很熟，一被问“为什么必须互素”，就答不上来了。而这恰恰是证明里最见功夫的地方。

我个人的看法是：欧拉函数的积性证明，是初等数论里少有的、能用三四种完全不同的路子走通、并且每条路都能反过来加深理解的命题。走完这几条路，你对“互素”“剩余系”“中国剩余定理”这几个概念的理解会上一个台阶，而不只是多背一个公式。

2. 开工之前：定义、约定和几块必须握在手里的砖

2.1 定义里的那个“1”到底算不算

欧拉函数 φ(n) 的定义是：小于等于 n 的正整数中，与 n 互素的数的个数。按这个定义，φ(1) = 1，因为 1 和 1 的最大公因数是 1，算互素。这个约定很多人不习惯，觉得“1 跟谁都不互素”，其实是把“互素”和“有没有公共素因子”搞混了——1 没有素因子，自然不会和任何数共享素因子。

定义域是正整数，值域也是正整数。φ(1) = 1 这个约定在积性讨论里非常关键：如果不认这个约定，φ 就不是积性函数了，因为任何积性函数 f 都要求 f(1) = 1（由 f(1) = f(1·1) = f(1)² 推出）。这一点在证明里经常被忽略，写作业时漏掉“φ(1) = 1”的说明，往往会被扣分。

我用一个更直白的记法：φ(n) 数的是1 到 n 这个区间里，与 n 没有共同素因子的数的个数。n 自己算不算？n ≥ 2 时 n 和 n 当然不互素，所以自动排除；n = 1 时区间只有 1，1 与自己互素，所以 φ(1) = 1。这样记，边界情况就不会出错。

2.2 积性和完全积性，差的是一个“门槛”

先把两个容易混的概念分清：

完全积性的典型代表是恒等函数 id(n) = n，以及刘维尔函数那一类。欧拉函数不行，原因很直观：φ 描述的是“与 n 互素的密度”，而“互素”这件事对素因子的重复次数是敏感的。φ(4) 数的是 1 到 4 里与 4 互素的数，只有 1 和 3 两个；φ(2)·φ(2) 相当于把 4 当成两个独立的 2 拼起来，可 2 和 2 根本不互素，重复的素因子被算了两次，自然对不上。

所以说，gcd(m,n)=1 不是证明的技术性假设，而是结论成立的本质条件。后面第 3 节会看到，这个条件在证明里扮演的是“让表格的每一列模 m 恰好跑遍完全剩余系”的角色，一旦不互素，这个跑遍性立刻失效。

2.3 三块基础砖：互素的传递、模运算下的 gcd、完全剩余系

证明要用到的东西不多，但每一条都得说清楚，不然写到一半会卡住。

第一块：gcd(a, n) 只由 a mod n 决定。这条来自带余除法和欧几里得算法：设 a = qn + r，则 gcd(a, n) = gcd(r, n)。它意味着“一个数是否与 n 互素”这件事，可以只看它除以 n 的余数。这是把无限多的整数问题压缩到 n 个余数上的关键。

第二块：gcd(m, n) = 1 时，若 m | kn，则 m | k。这是欧几里得引理的直接推论，也叫“互素可约”。它在证明里用来保证“同一列的数模 m 两两不同”。写法是：若 (r₁-r₂)n ≡ 0 (mod m)，因为 gcd(m,n)=1，所以 m | (r₁-r₂)，而 |r₁-r₂| < m，故 r₁ = r₂。

第三块：完全剩余系。模 m 的完全剩余系是 m 个两两不同余模 m 的整数，标准代表是 0, 1, …, m-1。一个常用结论是：若 gcd(c, m) = 1，则 a₁, …, a_m 是模 m 的完全剩余系时，ca₁, …, ca_m 也是。这条在证明“某列模 m 跑遍”时可以直接引用。

提示：第三块砖有个容易踩的坑——很多人会顺手写成“乘以任意 c 仍是完全剩余系”，漏掉 gcd(c, m)=1。这个条件在这里是必需的，不是可选的。

把这三块砖握稳，后面的表格法基本就是“把砖按顺序放下”的过程，不会有跳跃。

3. 主线证明：把 1 到 mn 摆成一张表，用两次筛选拿下

3.1 一个朴素的排版动作，把二维问题摊平

要证 φ(mn) = φ(m)φ(n)，最直接的想法是：φ(mn) 数的是 1 到 mn 里与 mn 互素的数，那就把这 mn 个数摆成一张 m 行 n 列的表，然后分两步筛。

具体排法：第 r 行第 s 列的格子放数

$$a_{r,s} = (r-1)n + s, \quad r = 1, 2, \ldots, m; \quad s = 1, 2, \ldots, n.$$

这样排列的好处是：r 从 1 走到 m、s 从 1 走到 n，a_{r,s} 恰好从 1 走到 mn，不重不漏。而且每一行是连续的 n 个数，每一列是间隔为 n 的 m 个数，这两种结构分别对应“模 n”和“模 m”，正好把 mn 的两个因子拆开了。

我试过用别的排法，比如按 n 行 m 列摆，结论一样但后面写坐标会别扭；也试过让 s 走外层、r 走内层，公式会变成 (s-1)m + r，本质相同。选 (r-1)n + s 这个形式，是因为列内相邻元素差 n，方便套用“gcd(m,n)=1 可约”这条引理。

3.2 第一刀按列筛：与 n 互素只看列号

固定一个数 a_{r,s}，看它和 n 的关系：

$$\gcd(a_{r,s}, n) = \gcd((r-1)n + s,\ n) = \gcd(s,\ n).$$

中间那一步用的是“加上 n 的倍数不改变与 n 的最大公因数”，也就是 2.3 里的第一块砖。这一步是整个证明的第一个转折点：它说明一整列里的 m 个数，要不全部与 n 互素，要不全部不与 n 互素，判定标准只看列号 s。

于是，要与 mn 互素，第一个必要条件是 gcd(s, n) = 1。s 的取值范围是 1 到 n，满足 gcd(s, n) = 1 的 s 有 φ(n) 个。换句话说，第一刀下去，m×n 个格子里只剩 φ(n) 列、共 m·φ(n) 个候选。

这一步很多人会写错，写成“筛选后剩下 φ(n) 个数”，把列数和个数搞混了。正确的说法是“剩下 φ(n) 列”，列里边还有 m 行待处理。我第一次写这个证明时就在这里翻过车，后面数出来是 φ(n) 而不是 mφ(n)，跟答案对不上，回头查了半天才发现是把“列”当成“格子”了。

3.3 第二刀按行筛：互素条件让每列恰好剩 φ(m) 个

现在剩下 φ(n) 列，每一列里还有 m 个数：a_{1,s}, a_{2,s}, …, a_{m,s}，它们分别是 s, n+s, 2n+s, …, (m-1)n+s。要从中挑出与 m 互素的。

关键观察是：这一列的 m 个数模 m 两两不同余。证明很干脆，假设 (r₁-1)n + s ≡ (r₂-1)n + s (mod m)，消去 s 得 (r₁-r₂)n ≡ 0 (mod m)。因为 gcd(m, n) = 1，由 2.3 的第二块砖得 m | (r₁-r₂)。而 r₁, r₂ 都在 1 到 m 之间，差的绝对值小于 m，只能是 r₁ = r₂。

m 个数、两两不同余模 m，所以它们恰好构成模 m 的一个完全剩余系。而完全剩余系里与 m 互素的元素个数，由定义就是 φ(m)。于是每一列里，与 m 互素的数恰好 φ(m) 个。

注意这个论证的美妙之处：它完全不依赖 s 是谁，任意一列都是 φ(m) 个。所以不需要逐列检查，直接乘：φ(n) 列 × 每列 φ(m) 个 = φ(m)φ(n) 个数。

3.4 合刀：为什么“与 mn 互素”等价于“两次都过关”

上面两步筛的是“与 n 互素”和“与 m 互素”，但我们的目标是“与 mn 互素”。这两件事等价吗？

等价。因为 mn 的素因子集合，恰好是 m 的素因子集合与 n 的素因子集合的并集（这里用到 gcd(m,n)=1，否则并集不是简单拼接，而是有重叠但又不完全重合，计数就乱了）。一个数与 mn 互素，当且仅当它不含 mn 的任何素因子，当且仅当它既不含 m 的素因子也不含 n 的素因子，当且仅当它与 m 互素且与 n 互素。

于是：

$$\varphi(mn) = #{a \le mn : \gcd(a,m)=1 \wedge \gcd(a,n)=1} = \varphi(n) \cdot \varphi(m).$$

证毕。整个证明只用了一次“排表”、一次“按列筛”、一次“按行筛”、一次“等价性说明”，没有引入任何额外工具，纯粹是初等的手法。这也是我偏爱这条主线的理由：它把“为什么互素”和“为什么能相乘”用同一张表解释了，而不是先记结论再补理由。

注意：第二刀能成立，靠的就是 gcd(m,n)=1 带来的“每列模 m 两两不同余”。若换成 m=2, n=2，表是 2 行 2 列：(1,2;3,4)。第一列 1、3 模 2 都余 1，根本不成完全剩余系，筛选就崩了。这就是第 2.2 节说的“门槛”。

3.5 从两个数推到一个标准分解式

有了两点积性，推到多个因子只是归纳的事：若 n = p₁^{α₁}p₂^{α₂}…p_k^{α_k}，则这些素数幂两两互素，反复用积性得

$$\varphi(n) = \prod_{i=1}^{k} \varphi(p_i^{\alpha_i}).$$

而 φ(p^α) 可以单独算：1 到 p^α 中与 p^α 不互素的数，恰好是 p 的倍数，共 p^{α-1} 个（p, 2p, …, p^{α-1}·p）。所以

$$\varphi(p^\alpha) = p^\alpha - p^{\alpha-1} = p^\alpha\left(1 - \frac{1}{p}\right).$$

代回去就是熟知的连乘积公式。到这里，公式的每一块都能追到证明的某一步，而不是天上掉下来的。

4. 换条路走：容斥原理和单位群同构，两种交叉验证

4.1 容斥的骨架：用“不是 p 的倍数”做筛子

主线证明走的是“结构性拆分”，另一条路是“直接计数”，用容斥原理硬算，好处是不需要先承认积性，可以直接得到连乘积公式，回头再验证积性，形成闭环。

思路：设 n 的不同素因子为 p₁, …, p_k。一个数不与 n 互素，当且仅当它是某个 p_i 的倍数。在 1 到 n 中，p_i 的倍数有 n/p_i 个，p_i p_j 的倍数有 n/(p_i p_j) 个，依此类推。按容斥：

$$\varphi(n) = n - \sum_i \frac{n}{p_i} + \sum_{i<j} \frac{n}{p_ip_j} - \cdots = n\prod_{i=1}^{k}\left(1 - \frac{1}{p_i}\right).$$

这个推导的每一步都很“算”，没有结构感，但胜在直接。它告诉我一件事：连乘积公式的每一项，对应容斥里的一个子集，展开后符号交替，最终合并成乘积形式。

如果要在这条路上验证积性，可以把 n = mn（互素）代进去，注意 mn 的素因子集合是两者不交的并集，连乘积自然分裂成两块，从而得到 φ(mn) = φ(m)φ(n)。这条路能走通，但它依赖已经证明的连乘积公式，逻辑上属于“先有鸡还是先有蛋”的次序问题，所以只适合当验证，不适合当第一证明。

4.2 单位群同构：最省字，但对基础要求最高

第三条路属于抽象代数口味。记 U(n) 为模 n 的简化剩余系（即模 n 乘法群，元素是与 n 互素的剩余类），那么 |U(n)| = φ(n)。当 gcd(m, n) = 1 时，映射

$$\psi: U(mn) \to U(m) \times U(n), \quad [a]_{mn} \mapsto ([a]_m, [a]_n)$$

是群同构。单射性来自中国剩余定理：若 a ≡ b (mod m) 且 a ≡ b (mod n)，则 a ≡ b (mod mn)；满射性也来自中国剩余定理：给定 ([x]_m, [y]n)，存在唯一的 [a]{mn} 同时满足两个同余式；保乘法运算是因为取余运算保乘法。

于是 |U(mn)| = |U(m)|·|U(n)|，即 φ(mn) = φ(m)φ(n)。三行写完。

这条路最干净，但它把“为什么能相乘”的答案简化成了“因为中国剩余定理”。对已经熟悉环同构的人，这是最优雅的；对刚接触数论的人，这相当于把难点藏起来了。我的建议是：先用第 3 节的表格法把直觉建立起来，再用这条同构视角做统一，两边对照，理解会扎实得多。

4.3 三种证法的对比：什么时候用哪条

这三条路给出的结论完全一致，但视角差别很大。表格法回答的是“数在哪里”，容斥法回答的是“数有多少”，同构法回答的是“结构是什么”。做研究或者写程序的时候，我通常用同构视角思考，用表格法验证细节，用容斥法做数值检查。三管齐下，出错概率会低很多。

5. 把它写成代码：让证明接受程序的检验

5.1 一份暴力实现，作为一切验证的基准

证明写完，我最习惯的动作是写一段最笨的代码去对答案。笨代码没有技巧，所以不容易错，可以当标尺用：

from math import gcd def phi_brute(n): """最朴素的定义式实现，用作基准""" if n == 1: return 1 return sum(1 for a in range(1, n + 1) if gcd(a, n) == 1)

这段代码的复杂度是 O(n log n)，跑 10⁵ 以内还凑合，再大就慢得不能忍。但它的价值不在速度，在于它和定义一字不差，任何优化实现的结果都必须和它保持一致。

我一般会先跑一个小表看看手感：

print([phi_brute(n) for n in range(1, 21)]) # [1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8]

看这几个值能发现两个现象：n > 2 时 φ(n) 全是偶数；素数 p 的 φ(p) = p - 1。前者可以用“a 与 n 互素则 n-a 也与 n 互素，且 a ≠ n-a（否则 n = 2a 且 gcd(a,n)=a，只有 a=1 时成立，即 n=2）”来证明，后者是定义直接推出。这两个观察在检查代码时很有用——如果跑出来某个 n > 2 的 φ(n) 是奇数，那一定是代码有 bug。

5.2 用积性做测试用例：这比随机抽查更狠

要验证积性，最直接的方式是枚举所有互素的数对：

def check_multiplicative(limit): phi = [0] * (limit * limit + 1) for i in range(1, limit * limit + 1): phi[i] = phi_brute(i) bad = [] for m in range(1, limit): for n in range(1, limit): if gcd(m, n) == 1 and phi[m * n] != phi[m] * phi[n]: bad.append((m, n)) return bad print(check_multiplicative(30)) # []

这段代码里有个细节值得说：φ(1) = 1 必须写对，否则 m = 1 或 n = 1 的用例会全线失败。很多人写 phi 函数时从 2 开始循环，把 1 的处理漏掉，一测积性就报错，还以为是证明有问题。

反过来，也可以故意测不互素的情形，看看“门槛”到底有多硬：

import math print(phi_brute(4), phi_brute(2) * phi_brute(2)) # 2, 1 print(phi_brute(8), phi_brute(2) * phi_brute(4)) # 4, 2 print(phi_brute(12), phi_brute(3) * phi_brute(4)) # 4, 4 （这个碰巧相等）

最后一组值得注意：φ(12) = 4，φ(3)·φ(4) = 2·2 = 4，恰好相等，但 3 和 4 确实互素，所以这不是反例。真正的不互素反例是前两组。这种“碰巧相等”的情况说明一点：不能用有限个用例去反推条件不必要，逻辑上必须靠证明说话。

5.3 大范围的线性筛：顺便把 φ 的分布摸一遍

实际工程里，φ 一般用筛法预处理到 10⁶ 或 10⁷。埃氏筛版本很好写：

def phi_sieve(N): phi = list(range(N + 1)) for p in range(2, N + 1): if phi[p] == p: # p 是素数 for j in range(p, N + 1, p): phi[j] -= phi[j] // p return phi

复杂度 O(N log log N)，够用。它的正确性直接来自连乘积公式：每遇到一个素因子 p，就把所有含 p 的数乘上 (1 - 1/p)。

线性筛版本更快，但要注意两个分支的写法：

def phi_linear(N): phi = [0] * (N + 1) phi[1] = 1 primes = [] is_comp = [False] * (N + 1) for i in range(2, N + 1): if not is_comp[i]: primes.append(i) phi[i] = i - 1 for p in primes: if i * p > N: break is_comp[i * p] = True if i % p == 0: phi[i * p] = phi[i] * p # p 已在 i 中出现，只乘 p break else: phi[i * p] = phi[i] * (p - 1) # 新素因子，乘 (p-1) return phi

这两个分支其实就是积性在代码里的投影：i % p == 0时 p 是 i 的素因子，φ(ip) = φ(i)·p；否则 p 是新素因子，φ(ip) = φ(i)·(p-1)。写错分支是最常见的线性筛 bug，症状是部分值偏大或偏小，用 5.1 的暴力版本一对就露馅。

心得：调试筛法时，我一般的顺序是——先对 N=100 和暴力版本逐项比对，再检查 φ(p) = p-1 对所有素数成立，再检查奇偶性规律，最后才跑大范围。逐项比对看着笨，但能直接定位到第一个出错的位置，比满屏随机抽查高效得多。

6. 常见问题与排查实录：证明写不下去时该翻哪一页

6.1 书写层面的高频错误清单

这些错误的共同点是：都不是思路错，而是中间某一步的表述含糊。含糊在平时不影响做题，一到大考或者正式写作就会暴露。我的习惯是把每一步都写成“对象 + 操作 + 依据”三件套，比如“固定第 s 列的所有 m 个数（对象），考察它们模 m 的余数（操作），因为 gcd(m,n)=1 所以两两不同余（依据）”。写全了三件套，别人挑不出空子，自己也理得顺。

6.2 三个值得反复琢磨的追问

追问一：为什么不能直接说“与 m 互素的有 φ(m) 个，与 n 互素的有 φ(n) 个，乘起来就行”？因为在 1 到 mn 里，这两个集合是重叠的，简单相乘会把重叠部分算两遍。表格法的价值就在于它把“重叠”处理成了“正交”——列管 n，行管 m，两者互不干扰，这才使得乘法合理。

追问二：如果不互素，究竟哪一步先崩？是第一刀之后的行结构崩。第一刀按列筛仍然成立（gcd(a,n) 只由 a mod n 决定，这一步不需要 m、n 互素），但第二刀里“每列模 m 两两不同余”不再成立，一列里可能有两个数同余，就数不出 φ(m) 个。所以积性证明的“命门”在第二刀。

追问三：能不能用“约分”的视角理解连乘积？可以，而且这个视角很直观。φ(n)/n 是 1 到 n 中与 n 互素的数的比例。对素数 p，比例是 1 - 1/p；对不同素因子，因为“是不是 p 的倍数”这些事件在互素的模数下互相独立，比例可以连乘。这就是连乘积公式的概率化解释。当然，这个解释只是帮助理解，正式证明还得回到 3.4 的等价性论证。

6.3 手算速查：几类典型数的 φ 值

手算时的经验是：先把 n 拆干净，再算比例，最后乘回去。不要一上来就套公式，容易把 1-1/p 里的 p 抄错。比如 1001 = 7×11×13，如果抄成 7×11×17，结果会差一大截。拆解阶段花的时间，远少于回头查错的时间。

7. 一点延伸：积性之外还能往哪走

欧拉函数积性证完之后，有两件事可以顺势做下去，一个偏理论、一个偏应用。

理论方向是恒等式 Σ_{d|n} φ(d) = n。它的一个漂亮证法是把 1 到 n 的每个数按 gcd(k, n) 分类：设 gcd(k, n) = d，则 k/d 与 n/d 互素，这样的 k 有 φ(n/d) 个。把所有 d 求和，就得到 Σ_{d|n} φ(n/d) = n，换元即得原式。这个恒等式和积性一起，构成了 φ 的两条主干性质。

应用方向是任何涉及模幂运算的场景。比如需要构造一个“乘法可逆”的剩余类系统时，φ(n) 给的就是可逆元素的个数，欧拉定理 a^{φ(n)} ≡ 1 (mod n)（gcd(a,n)=1）就是从这个计数直接推出来的。我实际写代码时，φ 最常见的用途就是判断某个模数下有多少个可逆元，以及做指数上的化简。

最后分享一个我自己踩过的小坑。最早学积性时，我以为“只要 m、n 不同就能乘”，用 φ(6) 和 φ(10) 试了一下，φ(60) = 16，而 φ(6)·φ(10) = 2×4 = 8，对不上，才意识到条件写错了。后来养成习惯：只要看到“积性”两个字，第一反应去查 gcd，第二反应去查 φ(1)。这两个检查点能挡掉绝大多数低级错误。

至于证明本身，我建议至少手写三遍：第一遍照着表格法抄，第二遍合上资料自己排表，第三遍试着用单位群同构重写一次。三遍下来，这个证明就不再是“背过的结论”，而是能随时调用的工具了。