翻旧笔记的时候看到当年学初等数论的一点记录书上刚讲完欧拉函数的定义紧接着就抛出积性然后直接把 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) 21 到 4 里与 4 互素的是 1 和 3而 φ(2)·φ(2) 1 × 1 1。两边不等。再取 m 2、n 4gcd 2φ(8) 41、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 21 × 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 全列出来、逐个求 gcd360 次按积性算只需要三次素数幂计算φ(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放的是 km1 到 kmm第 j 列j 从 1 数到 m放的是 j、mj、2mj、…、(n−1)mj。摆好之后有两个观察这两个观察一合结论就出来了。第一个观察是同一行里的数模 m 余数相同都是 j所以 gcd(kmj, m) gcd(j, m)。这意味着与 m 互素这件事只跟列号有关同一列的 m 个数要么全都与 m 互素要么全都不互素。于是与 m 互素的数恰好分布在 φ(m) 列里。第二个观察是同一列里的数模 n 两两不同余。第 j 列的两个数 j km 和 j km如果模 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) 1m 和 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 三条路线摆在一起比较路线核心工具优点代价适合场景甲单位群同构中国剩余定理一句话见本质可直接推广到多个因子依赖 CRT初等性稍弱已经学过 CRT想理解为什么会有积性乙方阵枚举完全剩余系 同余图形直观只用初等事实边界清楚多因子推广要归纳第一次学、需要把每一步都钉死丙容斥容斥原理顺手拿到通项公式顺序倒置信息量过剩已经掌握通项公式想快速回收积性我自己的习惯是讲给别人听的时候走乙因为方阵一画出来为什么需要 m 与 n 互素这个问题会自动暴露在第二个观察里自己回忆的时候走甲因为一句话就能想起来写代码或者做数值验证的时候走丙因为通项公式本来就是代码要用的东西。三条路线不是互相替代的关系是三把不同场合的锤子。3. 方阵证法逐句拆解每一句为什么成立3.1 排布约定与两个同一行同一列的观察方阵证法最容易出错的地方不是思路而是下标。所以先把约定钉死把 1 到 mn 按自然顺序填入 n 行 m 列行号用 k 表示从 0 数到 n−1列号用 j 表示从 1 数到 m。这样第 k 行第 j 列的元素就是 km jk 0 时第一行是 1 到 mk 1 时第二行是 m1 到 2m一直到最后一行 km j 取 k n−1、j m 得到 (n−1)m m nm正好收尾。如果行号从 1 开始数元素表达式就变成 (k−1)m jk 的范围是 1 到 n公式里多了一个减一推导时极容易在n | (k−k)m那一步把 k 的范围写成 0 到 n 而得出错误的结论。这个坑我在批改别人的手写证明时见过不止一次错误往往不是理解错了而是下标差一导致只能 k k这个断言站不住。建议一开始就用偏移量表述写代码时也一样。排好之后第 j 列的 n 个数是 j、jm、j2m、…、j(n−1)m第 k 行的 m 个数是 km1、km2、…、kmm。这两个方向要分开看行的方向对应模 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 kmk 0, 1, …, n−1。要是这一列里有两个数模 n 同余也就是 j km ≡ j km (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 ≠ 1m 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 两组数字走一遍m3,n5 和 m4,n9理论说完了拿两组互素的数把方阵真摆一遍比看十遍公式管用。先看 m 3、n 5mn 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、144 个。第 3 列 3、6、9、12、15模 5 是 3、1、4、2、0与 5 互素的是 3、6、9、124 个。再看列筛选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 9mn 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 3gcd(1,4) gcd(3,4) 1j 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 9gcd 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 × 25gcd(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(kmj, 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
