作业帮 > 综合 > 作业

求小于正整数i的所有与i互质的正整数之和,用欧拉函数

来源:学生作业帮 编辑:百度作业网作业帮 分类:综合作业 时间:2024/06/16 16:43:29
求小于正整数i的所有与i互质的正整数之和,用欧拉函数
f(i)=φ(i)*i/2有这个公式吗?怎么来的
求小于正整数i的所有与i互质的正整数之和,用欧拉函数
公式正确.
对于小于 i 且与 i 互质的数 x ,必定有 i-x 与 i 互质.
设小于 i 且与 i 互质的数分别为x1,x2,x3 …… xn
所以 f(i)=x1+x2+x3+...+xn=x1+x2+x3+...+(i-x3)+(i-x2)+(x-x1)=i*n/2
因为n=φ(i)
所以f(i)=φ(i)*i/2