题目

求：φ(n)＝ (1/3)n 的所有正整数n.
补充：φ(n)是欧拉函数 ：
欧拉函数是数论中很重要的一个函数,欧拉函数是指：对于一个正整数 n ,小于 n 且和 n 互质的正整数（包括 1）的个数,记作 φ(n) .

提问时间：2021-10-14

答案

n=p1^a1*p2^a2*……*pk^ak
则φ(n)=p1^(a1-1)*(p1-1)*p2^(a2-1)*(p2-1)*……*pk^(ak-1)*(pk-1)=n/3
显然n=3^a2^k,可以
因为φ(n)=3^(a-1)*(3-1)*2^(k-1)*(2-1)=3^(a-1)*2^k=n/3
若还有其他的因数
则φ(n)=3^(a-1)*(3-1)*2^(k-1)*(2-1)p3^(a3-1)*(p3-1)*p4^(a4-1)*(p4-1)*……*pk^(ak-1)*(pk-1)
=n/3*p3^(a3-1)*(p3-1)*p4^(a4-1)*(p4-1)*……*pk^(ak-1)*(pk-1)
因为p3〉=5
所以p3^(a3-1)*(p3-1)*p4^(a4-1)*(p4-1)*……*pk^(ak-1)*(pk-1)不等于1,所以φ(n)>n/3
若不含有3^a
则n/3不是整数
若没有2^k,则n是奇数
而φ(n)=3^(a-1)*(3-1)*p3^(a3-1)*(p3-1)*p4^(a4-1)*(p4-1)*……*pk^(ak-1)*(pk-1)是偶数
所以
n=3^a2^k