欧拉函数泛化：如何计算满足gcd(k,n)=d的k的个数？

这其实是欧拉函数的经典扩展应用，咱们一步步拆解来看：

首先得明确一个核心前提：只有当d是n的正约数时，才存在满足条件的k；如果d不能整除n，那么满足gcd(k,n)=d的k的个数直接为0。毕竟如果d都不是n的约数，k和n的最大公约数怎么可能等于d呢？

当d确实是n的正约数时，我们可以通过变量替换把问题转化成欧拉函数能解决的形式：

• 令 k = d * m，同时设 n' = n / d（因为d是n的约数，所以n'一定是整数）
• 原条件 gcd(k, n) = d 等价于 gcd(d*m, d*n') = d
• 根据最大公约数的性质，gcd(d*m, d*n') = d * gcd(m, n')，两边除以d后，就得到 gcd(m, n') = 1
• 再看k的范围：k是≤n的正整数，所以 d*m ≤ n → m ≤ n/d = n'，也就是m是≤n'的正整数

到这里问题就简化了：求≤n'且与n'互质的正整数m的个数——这正好是欧拉函数φ(n')的定义！

总结公式 #

• 若d不是n的正约数，满足条件的k的个数为 0
• 若d是n的正约数，满足条件的k的个数为 φ(n/d)（φ为欧拉函数）

举个例子验证 #

比如n=12，d=2：

• n/d=6，φ(6)=2（与6互质的数是1、5）
• 对应的k是2×1=2、2×5=10，检查gcd(2,12)=2、gcd(10,12)=2，确实是2个，和结果一致。

再比如n=15，d=3：

• n/d=5，φ(5)=4（与5互质的数是1、2、3、4）
• 对应的k是3、6、9、12，gcd(k,15)都是3，正好4个，完全符合结论。

内容的提问来源于stack exchange，提问作者Anjkhade