基于欧拉函数积性定理，求满足φ(n)=n/3的所有正整数n

嘿，咱们就用你提到的欧拉函数乘积公式一步步拆解这个问题，思路超清晰的！

首先回忆给定的定理：若(n = \prod p^c)（(p)是素数，(c)是正整数），则
φ(n) = n * ∏_{p|n} (1 - 1/p)

题目要求(φ(n) = n/3)，把定理代入后，两边可以约掉正整数(n)（(n≠0)），得到关键等式：
∏_{p|n} (1 - 1/p) = 1/3

把左边的((1-1/p))改写为((p-1)/p)，等式变形为：
∏_{p|n} (p-1)/p = 1/3
交叉相乘后得到：
3 * ∏_{p|n} (p-1) = ∏_{p|n} p

接下来咱们分析(n)的素因子：

• 首先，3必须是(n)的素因子：如果3不是(n)的素因子，右边的乘积里就没有3，左边乘了3之后不可能等于右边（右边是其他素数的乘积，不含3因子），矛盾。所以3一定在(n)的素因子中。
• 把3从乘积中单独拎出来，代入等式：
  左边 = (3*(3-1)∏_{p|n, p≠3} (p-1) = 32∏_{p|n, p≠3} (p-1))
  右边 = (3∏_{p|n, p≠3} p)
  约掉两边的3，得到：2 * ∏_{p|n, p≠3} (p-1) = ∏_{p|n, p≠3} p

现在看剩下的可能素因子：

• 假设(n)有除了3之外的素因子(p≥5)：那((p-1))是偶数（因为(p)是奇素数），但(p)本身是≥5的奇素数，它无法整除左边的乘积——左边的乘积是2乘以其他((p'-1))的乘积，而每个((p'-1))都小于(p)（因为(p)是更大的素因子），所以(p)不能整除任何((p'-1))，也不能整除2，这就导致右边的乘积包含(p)，左边却没有(p)的因子，矛盾。所以(n)不能有≥5的素因子。
• 那2能不能作为(n)的素因子？当然可以！如果(n)包含2，那((2-1)=1)，代入上面的等式：左边=2*1=2，右边=2，刚好成立。而且如果(n)有多个2的幂次（比如(2^{a)，(a≥0)），(φ(2}a)=2^a - 2^{a-1}=2{a-1})（当(a≥1)时），或者(φ(1)=1)（当(a=0)时），这时候结合3的幂次，(φ(n)=φ(2^a)*φ(3b)=2^{a-1}*2*3{b-1}=2^a*3{b-1}=n/3)，完全满足条件。

最后总结一下：
所有满足(φ(n)=n/3)的正整数(n)，都是形如n=2^a * 3^b的数，其中：

• (a)是非负整数（(a≥0)，也就是可以不包含2的因子，或者包含任意多个2的因子）
• (b)是正整数（(b≥1)，必须至少包含一个3的因子）

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