翻旧笔记的时候看到当年学初等数论的一点记录：书上刚讲完欧拉函数的定义，紧接着就抛出积性，然后直接把 1 到 mn 的数码成一个 n 行 m 列的方阵，指着某一列说"这里恰好有 φ(n) 个数与 n 互素"，一句话带过就乘起来了。当时我能把每一步抄下来，却说不清为什么非得这么摆、为什么"m 与 n 互素"这个条件在整段证明里只被提了一句却好像无处不在、为什么最后那一步乘法不算耍赖。后来陆陆续续有人拿同样的问题来问我，我才意识到卡在同一处的不是个别人，而是这条证明路线本身就有一个不太显眼的断层。这篇就把欧拉函数积性的证明从头到尾拆开讲透，包括三条不同路线的取舍、方阵证法每一句的成立理由、以及几个看着不痛不痒但会让证明直接失效的坑。适合同样在学初等数论、能看懂同余但还没把证明逻辑理顺的人，也适合只是想把这段结论用起来、不想深究的人——前半部分讲原理，后半部分讲怎么用。

1. 欧拉函数到底在数什么，积性又在承诺什么

1.1 定义里两个容易被跳过的地方

欧拉函数 φ(n) 的定义是：在 1 到 n 这 n 个整数中，与 n 互素的整数的个数。这个定义第一眼看上去很朴素，但它里面藏了两个容易被跳过的细节，而这两个细节在后面证明的边界处理上会直接影响对错。

第一个细节是 φ(1) = 1。按定义，1 到 1 之间只有整数 1，而 gcd(1,1) = 1，所以 φ(1) = 1，不是 0。这个值看起来无关紧要，但在积性函数的理论里它是必须钉死的：积性的意义在于"局部信息的拼接"，如果 φ(1) 取 0，那么任何涉及 φ(1) 的乘积式都会崩掉，比如后面会提到的卷积式 φ = μ * id 在 n = 1 处就对不上了。很多人复查代码时会发现 φ(1) 算出来是 0 或者 1 不一致，根源就在定义的理解上。

第二个细节是"与 n 互素"这句话里的 n 是固定不动的，变的是被数的那个整数。这听起来像废话，但初学者算错的时候十有八九是把对象搞反了，比如把"1 到 12 中与 12 互素的数"数成了"1 到 12 中 12 与它互素的数"，然后开始纠结 12 和谁互素。正确的动作是：把 1 到 n 全部列出来，对每一个数 a 算一次 gcd(a, n)，看是不是等于 1。用 12 举例，1 到 12 里与 12 互素的是 1、5、7、11，一共 4 个，所以 φ(12) = 4。这个逐个算的过程在 n 小的时候最可靠，也是后面验算积性最直接的手段。

顺带说一句，φ(n) 也常被叫作"模 n 的既约剩余类的个数"。这个说法听起来高级，其实就是把上面数出来的那批数按模 n 的余数归类，同一类里取一个代表。因为与 n 互素的数模 n 之后仍然与 n 互素，而且同一个剩余类里的数要么全都与 n 互素、要么全都不互素，所以"个数"这个概念在剩余类上是有意义的。这个视角在路线甲里会变成主角。

1.2 积性的条件是 gcd(m,n)=1，不是可选项

积性的正式表述是：如果 gcd(m, n) = 1，那么 φ(mn) = φ(m)φ(n)。很多人第一次读这句话，注意力全在等式上，把前面那半句当成了礼节性的开场白。实际上那半句才是这个定理的骨架，等式只是骨架上的肉。

为了说明它有多关键，直接看反例。取 m = n = 2，此时 gcd(2, 2) = 2，不互素。φ(4) = 2（1 到 4 里与 4 互素的是 1 和 3），而 φ(2)·φ(2) = 1 × 1 = 1。两边不等。再取 m = 2、n = 4，gcd = 2，φ(8) = 4（1、3、5、7），φ(2)·φ(4) = 1 × 2 = 2，还是不等。所以这个条件不是"通常情况下成立"的修饰语，而是去掉之后结论立刻失效的硬约束。

那如果把条件放宽一点，能不能得到一个修正版？能，而且形式很整齐：设 d = gcd(m, n)，则 φ(mn) = φ(m)·φ(n)·d / φ(d)。拿刚才两个例子验一下：m = n = 2 时 d = 2，φ(2)φ(2)·2/φ(2) = 1 × 1 × 2/1 = 2，等于 φ(4)，对上了；m = 2、n = 4 时 d = 2，1 × 2 × 2/1 = 4，等于 φ(8)，也对上了。这个修正版的推导要用到通项公式，属于"有了通项公式之后的推论"，但它至少说明一件事：积性失效不是随机的，失效的程度恰好由两边的公共素因子决定。理解了这一点，就不会再把 gcd(m,n)=1 当成一句可以忽略的附注。

顺便提醒，积性和"完全积性"是两个不同的概念。完全积性要求对任意 m、n 都有 f(mn) = f(m)f(n)，不做互素限制。φ 只是积性，不是完全积性，这个区别在第 4 节会专门拿 φ(4) 当反例讲清楚。

1.3 这个性质真正的价值：把 n 的长度压到素因子上

知道了积性是什么，接下来要回答的是"为什么要费劲证它"。答案很实际：它把一个关于任意 n 的计算，压缩成了一堆关于素数幂的计算。

任何一个大于 1 的整数 n 都能唯一分解成 n = p₁^a₁ · p₂^a₂ · … · p_r^a_r，其中 p_i 是互不相同的素数。这些素数幂两两互素，于是积性可以反复套用，得到 φ(n) = φ(p₁^a₁)·φ(p₂^a₂)·…·φ(p_r^a_r)。而素数幂上的值极其好算：1 到 p^k 中与 p^k 不互素的只有 p 的倍数，共 p^(k-1) 个，所以 φ(p^k) = p^k − p^(k-1)。两步一拼，通项公式就出来了。

这个压缩有多值钱，可以拿一个具体数字感受一下。n = 360 = 2³ × 3² × 5。按定义算，你得把 1 到 360 全列出来、逐个求 gcd，360 次；按积性算，只需要三次素数幂计算：φ(8) = 8 − 4 = 4，φ(9) = 9 − 3 = 6，φ(5) = 5 − 1 = 4，乘起来 4 × 6 × 4 = 96。验算一下 360 × (1/2) × (2/3) × (4/5) = 360 × 8/30 = 96，对得上。当 n 涨到几十位的时候，这个差距不是几倍的问题，是能不能算出来的问题。

还有一层价值是理论上的。很多数论结论的证明模式都是这样：先证某个函数是积性的，然后宣称"只需在素数幂上验证"，一句话就把无限多种情况砍掉。这条路子在后面的第 6 节会再出现一次，用来证 Σ_{d|n} φ(d) = n。所以积性不只是 φ 的一个性质，它更像是一把可以反复借用的工具。

2. 三条证明路线的取舍：环同构、摆方阵、容斥

2.1 路线甲：把 φ 看成单位群的阶

最短的证明来自剩余类的语言。φ(n) 等于模 n 的既约剩余类的个数，而模 n 的既约剩余类在乘法下构成一个群，记作 (Z/nZ)^×，它的阶就是 φ(n)。这一步只是换了个说法，真正的活儿在下一步。

当 gcd(m, n) = 1 时，中国剩余定理给出一个环同构：Z/mnZ ≅ Z/mZ × Z/nZ。同构的意思是两边元素一一对应，而且加法和乘法都保持。既然是环同构，它自然把可逆元映到可逆元，把不可逆元映到不可逆元——因为"可逆"这个性质是用乘法定义的，而同构保持乘法。于是它进一步诱导出单位群之间的同构：(Z/mnZ)^× ≅ (Z/mZ)^× × (Z/nZ)^×。

到这里就结束了。同构的两边阶数相等，左边是 φ(mn)，右边两个群的阶相乘是 φ(m)·φ(n)，所以 φ(mn) = φ(m)φ(n)。

这条路线的好处是"一句话说清本质"：积性根本不是 φ 的专属性质，而是中国剩余定理在单位群上的直接投影。任何靠剩余类定义出来的乘法函数，只要互素条件成立，都会自动积性。坏处是它把重量压在了中国剩余定理上——而 CRT 本身的存在唯一性证明并不比我们要证的结论轻多少。所以如果是初等数论的课堂，这条路线通常被当成"事后回看"，而不是第一遍的证明。

2.2 路线乙：把 1 到 mn 码成 n 行 m 列的方阵

这是教科书里最常见、也最适合初学的一版，因为它把互素这个条件变成了一眼能看见的图形，不需要预先搬出 CRT。核心动作是：把 1 到 mn 这 mn 个数，按顺序填进一个 n 行 m 列的方阵，第 k 行（k 从 0 数到 n−1）放的是 km+1 到 km+m，第 j 列（j 从 1 数到 m）放的是 j、m+j、2m+j、…、(n−1)m+j。

摆好之后有两个观察，这两个观察一合，结论就出来了。

第一个观察是同一行里的数模 m 余数相同，都是 j，所以 gcd(km+j, m) = gcd(j, m)。这意味着"与 m 互素"这件事只跟列号有关，同一列的 m 个数要么全都与 m 互素，要么全都不互素。于是与 m 互素的数恰好分布在 φ(m) 列里。

第二个观察是同一列里的数模 n 两两不同余。第 j 列的两个数 j + km 和 j + k'm，如果模 n 同余，就有 n | (k − k')m，而 gcd(m, n) = 1，所以 n | (k − k')，但 k、k' 都在 0 到 n−1 之间，只能 k = k'。因此这一列的 n 个数恰好构成模 n 的一个完全剩余系，其中与 n 互素的正好是 φ(n) 个。

两个观察拼起来：与 mn 互素等价于同时与 m 和与 n 互素（因为 mn 的素因子就是 m 和 n 的素因子合起来），所以只需先挑出那 φ(m) 列，再在每列里数出 φ(n) 个，总数 φ(m)·φ(n)。而整个方阵恰好把 1 到 mn 走了一遍，不重不漏，所以 φ(mn) 就等于这个总数。

这条路线只用到两样东西：模 m 同余的性质，以及"m 与 n 互素时 km 模 n 跑遍完全剩余系"这个初等事实。门槛低，图形直观，缺点是不容易推广到三个以上因子——虽然可以归纳着做，但每次归纳都要重新摆一次方阵，观感上不如路线甲利落。

2.3 路线丙：容斥先出通项公式，再回头拿积性

第三条路是先证通项公式，再从通项公式读出积性。做法是标准的容斥：设 n 的素因子为 p₁, …, p_r，令 A_i 表示 1 到 n 中被 p_i 整除的数构成的集合，那么与 n 互素的数就是不在任何 A_i 里的数，用容斥原理展开，得到 φ(n) = n·∏(1 − 1/p_i)。

要证积性，就看 mn 的素因子集合。因为 gcd(m, n) = 1，m 和 n 没有公共素因子，所以 mn 的素因子集合恰好是两者之并，而且是不交并。不交并上的乘积可以直接拆成两个乘积相乘：∏_{p|mn}(1 − 1/p) = ∏_{p|m}(1 − 1/p) · ∏_{p|n}(1 − 1/p)。两边同乘 mn，右边拆成 m·∏_{p|m}(…) 和 n·∏_{p|n}(…)，正好是 φ(m)·φ(n)。

这条路走得通，但它有个逻辑顺序上的问题：它实际上是"先证明了通项公式，然后发现通项公式在互素时能拆"。而通项公式本身的容斥推导，用到的信息量比积性更多。所以从教学效率上讲，这是绕远了；从逻辑严密性上讲，它没问题，只是把简单结论放在了复杂工具之后。真正要警惕的是它的"山寨版"——还没证通项公式，就默认通项公式成立，再用它去证积性，那就是循环论证了，第 4 节会专门说。

2.4 三条路线摆在一起比较

我自己的习惯是：讲给别人听的时候走乙，因为方阵一画出来，"为什么需要 m 与 n 互素"这个问题会自动暴露在第二个观察里；自己回忆的时候走甲，因为一句话就能想起来；写代码或者做数值验证的时候走丙，因为通项公式本来就是代码要用的东西。三条路线不是互相替代的关系，是三把不同场合的锤子。

3. 方阵证法逐句拆解：每一句为什么成立

3.1 排布约定与两个"同一行""同一列"的观察

方阵证法最容易出错的地方不是思路，而是下标。所以先把约定钉死：把 1 到 mn 按自然顺序填入 n 行 m 列，行号用 k 表示，从 0 数到 n−1，列号用 j 表示，从 1 数到 m。这样第 k 行第 j 列的元素就是 km + j，k = 0 时第一行是 1 到 m，k = 1 时第二行是 m+1 到 2m，一直到最后一行 km + j 取 k = n−1、j = m 得到 (n−1)m + m = nm，正好收尾。

如果行号从 1 开始数，元素表达式就变成 (k−1)m + j，k 的范围是 1 到 n，公式里多了一个减一，推导时极容易在"n | (k−k')m"那一步把 k 的范围写成 0 到 n 而得出错误的结论。这个坑我在批改别人的手写证明时见过不止一次，错误往往不是理解错了，而是下标差一导致"只能 k = k'"这个断言站不住。建议一开始就用偏移量表述，写代码时也一样。

排好之后，第 j 列的 n 个数是 j、j+m、j+2m、…、j+(n−1)m，第 k 行的 m 个数是 km+1、km+2、…、km+m。这两个方向要分开看：行的方向对应模 m，列的方向对应模 n。这个"行看 m、列看 n"的对应关系不是随意的，它是由元素表达式 km + j 里 m 乘在行号上、j 是列号决定的——km 模 m 归零，所以行内的数模 m 都等于 j；而 j 固定时变化的是 km，所以列内变化的部分是 m 的倍数，模 n 的行为就由 m 与 n 的关系决定。

顺带说一句，你也可以摆成 m 行 n 列，结论一样，但那时候行对应 n、列对应 m，所有的叙述都要跟着翻一遍。两种摆法没有优劣，但一定要选定一种并且全程不改。中途换摆法是这类证明里第二常见的翻车原因。

3.2 列内为什么恰好有 φ(n) 个与 n 互素

这一句是整个证明里唯一用到 gcd(m, n) = 1 的地方，值得单独拆开。

第 j 列的数可以写成 j + km，k = 0, 1, …, n−1。要是这一列里有两个数模 n 同余，也就是 j + km ≡ j + k'm (mod n)，两边消掉 j 得 (k − k')m ≡ 0 (mod n)，即 n | (k − k')m。此时如果 gcd(m, n) = 1，就可以从乘积里把 m 拿掉，得到 n | (k − k')。而 k 和 k' 都是 0 到 n−1 之间的整数，它们的差落在 −(n−1) 到 n−1 之间，能被 n 整除的只有 0，所以 k = k'。

也就是说，这一列的 n 个数模 n 之后两两不同余。n 个数、n 个可能的余数、两两不同，那只能是恰好把 0 到 n−1 各占一次——这就是"构成模 n 的完全剩余系"。

完全剩余系有个非常好用的性质：其中与 n 互素的元素个数恒等于 φ(n)。理由很直接，一个数 a 与 n 互素，等价于 a 加上 n 的任意倍数之后仍与 n 互素，因为 gcd(a + tn, n) = gcd(a, n)。所以在模 n 的同一个剩余类里，互素性是一致的。完全剩余系每个剩余类恰好取一个代表，那么"与 n 互素的代表有几个"就等于"模 n 的既约剩余类有几个"，后者按定义就是 φ(n)。

把这两步串起来：列内 n 个数构成模 n 的完全剩余系，所以其中与 n 互素的恰好 φ(n) 个。注意这个结论对每一列都成立，而且不同列给出的数目相同，都是 φ(n)，这一点在下一步要用。

如果 gcd(m, n) = d > 1，第一步就断了：n | (k − k')m 只能推出 (n/d) | (k − k')，k 和 k' 的差可以是 n/d 的倍数而不为 0，于是列内会出现重复的剩余类，覆盖不满整个完全剩余系。举个最极端的例子，m = n = 2，第 1 列是 1 和 3，模 2 都是 1，只覆盖了一个剩余类，与 2 互素的有 2 个，而 φ(2) = 1。这就是反例的完整来龙去脉。

3.3 行条件为什么只跟列号有关

第二个观察处理的是"与 m 互素"。第 k 行第 j 列的元素是 km + j，对它求与 m 的最大公因数：gcd(km + j, m) = gcd(j, m)。这一步用的是最大公因数的一个基本性质——gcd(a + tb, b) = gcd(a, b)，把 km 看成 tb 就行。

这个等式说明，一个数与 m 是否互素，完全由它除以 m 的余数 j 决定，跟它具体在第几行没有关系。换句话说，同一列里的所有数，与 m 的互素性完全一致：要么整列都与 m 互素，要么整列都不互素。而哪些列与 m 互素，就是那些列号 j 满足 gcd(j, m) = 1 的列。

j 的取值范围是 1 到 m，这里面与 m 互素的个数是多少？按 φ 的定义，1 到 m 中与 m 互素的个数就是 φ(m)。需要注意的是 j = m 这一列，gcd(m, m) = m ≠ 1（m > 1 时），所以最后一列整列都被排除，这跟"φ(m) 数的是 1 到 m−1 中与 m 互素的个数"是一致的，因为 m 本身从来不计入。这个端点细节在第 4 节还会再提一次。

到这里，方阵被切成了两部分：φ(m) 列是"与 m 互素"的候选区，剩下的 m − φ(m) 列则整列作废，一个都不用数。这一步的漂亮之处在于它把"与 m 互素"这个条件从逐个元素判断，降级成了按列筛选，工作量从 mn 次降到 m 次。

3.4 最后那步乘法凭什么合法

现在有了两个结论：第一，与 m 互素的数恰好落在 φ(m) 列里，每列 n 个；第二，每一列里与 n 互素的数恰好 φ(n) 个。要得到"同时与 m 和与 n 互素的数有 φ(m)·φ(n) 个"，中间还差一步论证，这一步经常被省略，而省略之后整个证明就有了缺口。

缺口在哪？在于"每一列里与 n 互素的恰好 φ(n) 个"这个事实虽然对每列都成立，但成立的是数目相同，不是位置相同。如果不同列里那 φ(n) 个数的位置是乱的，你没法保证它们都落在同一批元素上。好在我们要数的东西不需要位置对齐：先把范围限定在那 φ(m) 列里，这 φ(m) 列一共有 φ(m)·n 个元素，每一列内部独立地贡献 φ(n) 个满足"与 n 互素"的元素，列与列之间互不重叠（方阵里每个位置只属于一列），所以总数就是 φ(m) 个 φ(n) 相加，等于 φ(m)·φ(n)。

关键的合法性来自两点：一是筛选的先后顺序明确，先按列筛 m，再在列内筛 n，两步筛的是同一个方阵里的元素，不存在漏掉或多算；二是每列贡献的数目恒定，才能用乘法代替加法。如果每列贡献的数目不一样，就只能老老实实求和。

还有一个收尾：为什么"同时与 m 和与 n 互素"就等于"与 mn 互素"？因为一个素数整除 mn 当且仅当它整除 m 或整除 n（这里用到 m、n 是整数这个平凡事实，不需要互素）。所以 a 与 mn 没有公共素因子，等价于 a 与 m 没有公共素因子且 a 与 n 没有公共素因子。这一步其实不依赖 gcd(m, n) = 1，互素条件只用在了 3.2 节。

3.5 两组数字走一遍：m=3,n=5 和 m=4,n=9

理论说完了，拿两组互素的数把方阵真摆一遍，比看十遍公式管用。

先看 m = 3、n = 5，mn = 15，摆成 5 行 3 列：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

第 1 列是 1、4、7、10、13，模 5 分别是 1、4、2、0、3，五个余数各不相同，是完全剩余系；其中与 5 互素的是 1、4、7、13，共 4 个，等于 φ(5) = 4。第 2 列 2、5、8、11、14，模 5 是 2、0、3、1、4，同样跑遍；与 5 互素的是 2、8、11、14，4 个。第 3 列 3、6、9、12、15，模 5 是 3、1、4、2、0；与 5 互素的是 3、6、9、12，4 个。

再看列筛选：j = 1 时 gcd(1,3) = 1，保留；j = 2 时 gcd(2,3) = 1，保留；j = 3 时 gcd(3,3) = 3，整列作废。所以保留 2 列，正是 φ(3) = 2。总数 2 × 4 = 8。直接数 1 到 15 中与 15 互素的：1、2、4、7、8、11、13、14，确实是 8 个，对上了。

再看 m = 4、n = 9，mn = 36，摆成 9 行 4 列：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

保留的列：j = 1 和 j = 3（gcd(1,4) = gcd(3,4) = 1），j = 2 和 j = 4 因为与 4 不互素被整列剔除，所以保留 2 列，等于 φ(4) = 2。

看第 1 列：1、5、9、13、17、21、25、29、33，模 9 分别是 1、5、0、4、8、3、7、2、6，九个余数各不相同。其中与 9 互素的（不能被 3 整除的）是 1、5、13、17、25、29，共 6 个，等于 φ(9) = 6。被剔除的是 9、21、33，三个都是 3 的倍数。第 3 列：3、7、11、15、19、23、27、31、35，模 9 是 3、7、2、6、1、5、0、4、8，同样跑遍；与 9 互素的是 7、11、19、23、31、35，也是 6 个。

总数 2 × 6 = 12。验算 φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 1/2 × 2/3 = 12，一致。这种"摆一遍 + 数一遍 + 公式验一遍"的三重核对，是我建议每一个初学时都亲手做一次的，做两组之后，证明里每一步在干什么就基本不会忘了。

4. 五个容易踩的坑，以及它们的反例

4.1 互素条件在哪一步被用掉

第一个坑是把 gcd(m, n) = 1 当成背景设定，觉得它一直在起作用。实际上整个方阵证明里，它只在一个地方被用到：证明"第 j 列的 n 个数模 n 两两不同余"这一步。除此之外的所有步骤——行内与 m 的互素性、列内互素个数等于 φ(n)、筛选的乘法、与 mn 互素的等价转化——全都不需要互素条件。

正因为只用了一次，很多人会忽略它，写证明的时候干脆不写"因为 gcd(m,n)=1，所以可以从 n | (k−k')m 推出 n | (k−k')"。这一句一省，论证就断了：从 n | (k−k')m 推 n | (k−k')，这一步用的是一个初等数论事实——若 gcd(a, b) = 1 且 a | bc，则 a | c。这里的 a 是 n、b 是 m、c 是 k−k'。条件不满足时这个推理直接失效。

反例前面给过：m = n = 2，第 1 列只有 1 和 3，模 2 全是 1，覆盖不满，列内与 2 互素的有 2 个而不是 φ(2) = 1。再看 m = 6、n = 9，gcd = 3，第 1 列是 1、7、13、19、25、31、37、43、49，模 9 是 1、7、4、1、7、4、1、7、4，只跑了三个剩余类，重复三遍。这时候再套"每列 φ(9) = 6 个"就错了。所以每次写这段证明，都应该在那一句后面明确标注"此处用了互素条件"，哪怕不展开，也要让读者知道重量压在哪里。

4.2 积性和完全积性不是一回事

第二个坑是把积性记成了"随便两个数相乘都行"。用 φ(2) 和 φ(4) 就能戳穿：φ(2) = 1，φ(4) = 2，φ(8) = 4。如果 φ 是完全积性的，应该有 φ(8) = φ(2)·φ(4) = 2，但实际是 4，不等。再看 φ(2)·φ(2) = 1 而 φ(4) = 2，也不等。

这个区别在实际使用中有具体后果。比如你要算 φ(100)，100 = 4 × 25，gcd(4, 25) = 1，可以用积性拆成 φ(4)·φ(25) = 2 × 20 = 40。但如果你要算 φ(8)，把它拆成 2 × 4 就错了，必须拆成 2³ 再按素数幂算 φ(8) = 8 − 4 = 4。判断能不能拆的唯一标准是两部分的 gcd 是不是 1，不是"看起来分得开"就行。

还有一个更隐蔽的版本：有人记成"φ(mn) = φ(m)φ(n)"但心里想的是对任意 m、n 成立，然后在程序里写了一个不检查互素的分解函数，结果在某些输入上对、某些输入上错，排查起来非常费劲。这种 bug 的讨厌之处在于它不是必现的，小数据测试很容易蒙混过关。稳妥的做法是在分解函数里显式断言 gcd 为 1，一旦违例立刻报错，而不是静默返回错误结果。

4.3 用通项公式证积性属于循环论证

第三个坑最隐蔽，因为它写出来的证明看起来完全正确。错误版本是这样的：先写 φ(n) = n∏(1 − 1/p)，然后说"因为 m 和 n 互素，素因子不交，所以乘积可以拆开，得到 φ(mn) = φ(m)φ(n)"。字面上每一句都对，但它证的不是积性，而是"在通项公式成立的前提下，积性成立"。

问题在于通项公式是怎么来的。标准的通项公式推导，要么走容斥，要么走"先用积性拆成素数幂、再算 φ(p^k)"。如果是后者，那通项公式本身就是积性的直接推论，用通项公式去证积性就是转了一圈回到原点；如果是前者，容斥的推导过程用到的信息量比积性更大，属于用大炮打蚊子，逻辑上不构成循环，但严格说是"先证了更强的结论"。

判断有没有循环，一个简单的办法是问自己：写到这一步为止，我用过的工具里有没有哪个本身就需要积性？如果答不上来，就老老实实走方阵路线，一步一步来。方阵路线的门槛最低，只要同余的基本性质，不容易出逻辑问题。

4.4 把"行"和"列"的结论直接相乘

第四个坑是跳步。方阵里有两个对称的结论：行内与 m 的互素性只跟列号有关，所以有 φ(m) 列合格；列内与 n 互素的恰好 φ(n) 个。有人直接写"所以总共 φ(m)·φ(n) 个"，中间不解释。

这个跳步在结论上是对的，但论证上是空的。因为这两个结论描述的是两类不同的筛选：一个是"整列的属性"，一个是"列内元素的属性"。要相乘，必须说明第一类筛选已经把候选范围缩成了 φ(m) 列，第二类筛选是在这个缩小后的范围里逐列进行的，并且每列贡献相同。少了这段说明，读者有理由怀疑你是不是把两个不同的计数对象混在一起了。

更容易出错的写法是完全颠倒的版本：先数"每行有 φ(m) 个数与 m 互素"，再数"每列有 φ(n) 个数与 n 互素"，然后说"两者独立相乘"。这个版本才是真的有问题，因为它没有说明那 φ(m) 个数在行内的位置是否与行号无关。好在对于 φ 这个具体情形，位置确实与行号无关（因为 gcd(km+j, m) = gcd(j, m) 里 k 消失了），所以结论仍然成立。但"结论仍然成立"和"论证已经完整"是两回事，前者靠运气（恰好独立），后者靠推导。写证明时应该走"先列后行"的版本，那个版本的每一步都是必然的。

4.5 端点 1 和 mn 的归属

第五个坑是边界值。方阵里有两个特殊位置：左上角的 1 和右下角的 mn。

1 在第一行第一列，gcd(1, m) = 1、gcd(1, n) = 1、gcd(1, mn) = 1，三处都合格，会被计入，这跟 φ 的定义一致（1 与任何正整数互素，且 φ(n) 数的是 1 到 n 的闭区间）。这一项不能漏，漏了会差 1。

mn 在最后一行最后一列，j = m。此时 gcd(mn, m) = m