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 时区间只有 11 与自己互素所以 φ(1) 1。这样记边界情况就不会出错。2.2 积性和完全积性差的是一个“门槛”先把两个容易混的概念分清概念定义欧拉函数是否满足反例积性gcd(m,n)1 时f(mn)f(m)f(n)是无完全积性对任意 m,nf(mn)f(m)f(n)否φ(4)2≠φ(2)φ(2)1乘性可加混合f(mn)f(m)f(n) 无附加条件否同上完全积性的典型代表是恒等函数 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 走到 na_{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, ns, 2ns, …, (m-1)ns。要从中挑出与 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 两两不同余”。若换成 m2, n2表是 2 行 2 列(1,2;3,4)。第一列 1、3 模 2 都余 1根本不成完全剩余系筛选就崩了。这就是第 2.2 节说的“门槛”。3.5 从两个数推到一个标准分解式有了两点积性推到多个因子只是归纳的事若 n p₁^{α₁}p₂^{α₂}…p_k^{α_k}则这些素数幂两两互素反复用积性得$$\varphi(n) \prod_{i1}^{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_{ij} \frac{n}{p_ip_j} - \cdots n\prod_{i1}^{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只有 a1 时成立即 n2”来证明后者是定义直接推出。这两个观察在检查代码时很有用——如果跑出来某个 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 的暴力版本一对就露馅。心得调试筛法时我一般的顺序是——先对 N100 和暴力版本逐项比对再检查 φ(p) p-1 对所有素数成立再检查奇偶性规律最后才跑大范围。逐项比对看着笨但能直接定位到第一个出错的位置比满屏随机抽查高效得多。6. 常见问题与排查实录证明写不下去时该翻哪一页6.1 书写层面的高频错误清单症状常见原因修正办法算出来是 φ(n) 而非 mφ(n)把“列”当成了“格子”明确每一步筛的是行集合还是列集合只说“每列与 m 互素的有一个”漏证两两不同余补欧几里得引理那一步证到一半卡在“等价性”没说明 mn 的素因子是并集用“不含素因子”的定义重述积性条件写成“m≠n”混淆互素与不相等明确写出 gcd(m,n)1φ(1) 处理错误定义边界没交代声明 φ(1)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分解式φ(n) 计算过程结果602²·3·560×(1/2)×(2/3)×(4/5)163602³·3²·5360×(1/2)×(2/3)×(4/5)9610017·11·131001×(6/7)×(10/11)×(12/13)72010242¹⁰1024 - 5125129993³·37999×(2/3)×(36/37)648手算时的经验是先把 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)。这两个检查点能挡掉绝大多数低级错误。至于证明本身我建议至少手写三遍第一遍照着表格法抄第二遍合上资料自己排表第三遍试着用单位群同构重写一次。三遍下来这个证明就不再是“背过的结论”而是能随时调用的工具了。 
长河君 · 2026/11/2 16:56:22 · 阅读 1.2k 欧拉函数积性证明：从剩余系筛选到线性筛实现
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 时区间只有 11 与自己互素所以 φ(1) 1。这样记边界情况就不会出错。2.2 积性和完全积性差的是一个“门槛”先把两个容易混的概念分清概念定义欧拉函数是否满足反例积性gcd(m,n)1 时f(mn)f(m)f(n)是无完全积性对任意 m,nf(mn)f(m)f(n)否φ(4)2≠φ(2)φ(2)1乘性可加混合f(mn)f(m)f(n) 无附加条件否同上完全积性的典型代表是恒等函数 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 走到 na_{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, ns, 2ns, …, (m-1)ns。要从中挑出与 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 两两不同余”。若换成 m2, n2表是 2 行 2 列(1,2;3,4)。第一列 1、3 模 2 都余 1根本不成完全剩余系筛选就崩了。这就是第 2.2 节说的“门槛”。3.5 从两个数推到一个标准分解式有了两点积性推到多个因子只是归纳的事若 n p₁^{α₁}p₂^{α₂}…p_k^{α_k}则这些素数幂两两互素反复用积性得$$\varphi(n) \prod_{i1}^{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_{ij} \frac{n}{p_ip_j} - \cdots n\prod_{i1}^{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只有 a1 时成立即 n2”来证明后者是定义直接推出。这两个观察在检查代码时很有用——如果跑出来某个 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 的暴力版本一对就露馅。心得调试筛法时我一般的顺序是——先对 N100 和暴力版本逐项比对再检查 φ(p) p-1 对所有素数成立再检查奇偶性规律最后才跑大范围。逐项比对看着笨但能直接定位到第一个出错的位置比满屏随机抽查高效得多。6. 常见问题与排查实录证明写不下去时该翻哪一页6.1 书写层面的高频错误清单症状常见原因修正办法算出来是 φ(n) 而非 mφ(n)把“列”当成了“格子”明确每一步筛的是行集合还是列集合只说“每列与 m 互素的有一个”漏证两两不同余补欧几里得引理那一步证到一半卡在“等价性”没说明 mn 的素因子是并集用“不含素因子”的定义重述积性条件写成“m≠n”混淆互素与不相等明确写出 gcd(m,n)1φ(1) 处理错误定义边界没交代声明 φ(1)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分解式φ(n) 计算过程结果602²·3·560×(1/2)×(2/3)×(4/5)163602³·3²·5360×(1/2)×(2/3)×(4/5)9610017·11·131001×(6/7)×(10/11)×(12/13)72010242¹⁰1024 - 5125129993³·37999×(2/3)×(36/37)648手算时的经验是先把 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)。这两个检查点能挡掉绝大多数低级错误。至于证明本身我建议至少手写三遍第一遍照着表格法抄第二遍合上资料自己排表第三遍试着用单位群同构重写一次。三遍下来这个证明就不再是“背过的结论”而是能随时调用的工具了。