作业帮1到60中与60互质的整数个数?为什么是n=(1-1/2)(1-1/3)(1-1/5)=16?1到60中与60互质的整数个数?为什么是n=(1-1/2)(1-1/3)(1-1/5)=16?求普遍解答方法
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/06 08:00:53
1到60中与60互质的整数个数?为什么是n=(1-1/2)(1-1/3)(1-1/5)=16?1到60中与60互质的整数个数?为什么是n=(1-1/2)(1-1/3)(1-1/5)=16?求普遍解答方法
1到60中与60互质的整数个数?为什么是n=(1-1/2)(1-1/3)(1-1/5)=16?
1到60中与60互质的整数个数?
为什么是n=(1-1/2)(1-1/3)(1-1/5)=16?
求普遍解答方法
1到60中与60互质的整数个数?为什么是n=(1-1/2)(1-1/3)(1-1/5)=16?1到60中与60互质的整数个数?为什么是n=(1-1/2)(1-1/3)(1-1/5)=16?求普遍解答方法
这是欧拉φ函数的公式：
φ(n)：小于n的数里,与n互质的数的个数.
公式是这样的：
先把 n 进行质因数分n = p1^k1 * p2^k2 * ...* pr^kr
则：φ(n) = n (1 - 1/p1) (1 - 1/p2) ...(1 - 1/pr)
比如：n = 60 = 2^2 * 3 * 5
那么：φ(n) = 60 * (1-1/2) (1-1/3) (1-1/5) = 16
再比如：n = 36 = 2^3 * 3^2
那么：φ(n) = 36 * (1-1/2) (1-1/3) = 12
证明是这样的.
先证明一个引理：如果 m、n 互质,则：φ(mn) = φ(m) φ(n)
然后质因数分解中,p1^k1、p2^k2、...、pr^kr 都是互质的,并且对于质数 p：
φ(p^k) = p^k - p^(k-1) = p^k (1-1/p)
所以乘起来后：
φ(n) = φ(p1^k1) φ(p2^k2) ...φ(pr^kr)
= p1^k1 (1-1/p1) * p2^k2 (1-1/p2) * ...* pr^kr (1-1/pr)
= n (1-1/p1) (1-1/p2) ...(1-1/pr)