求方程φ(x)=n的解的数量关于n的渐近阶的技术问询

Hey，咱们来拆解这个关于欧拉函数的问题——首先明确一下，我们把满足φ(x)=n的正整数x的个数记为N(n)，比如你给出的例子里，φ(x)=36有8个解，所以N(36)=8。现在要聊的是N(n)当n趋向无穷时的渐近行为。

核心结论：N(n)的最大渐近阶 #

目前数论里的经典结论是：

• 当n→∞时，N(n)的最大可能阶是 ( n^{\Theta\left(\frac{1}{\log \log n}\right)} )
• 换个更直观的说法，这个阶比任何固定幂次的多项式增长都慢（因为指数里的 ( \frac{1}{\log \log n} ) 会趋向0），但又比任何对数的幂次增长都快。

补充细节 #

• 不是所有n都有解：比如n=14，不存在任何x使得φ(x)=14，这类n的N(n)=0。实际上，能让方程有解的n（叫“欧拉商数”）在所有正整数里的密度是0——也就是说，几乎所有n对应的N(n)都是0。
• 当n确实有解时，N(n)的波动可以非常大：存在无穷多组n，使得N(n)达到上面提到的最大阶；同时也有很多n，即使有解，N(n)也很小（比如n是质数p时，φ(x)=p的解最多只有2个）。

简单理解思路 #

要理解这个渐近阶，可以从欧拉函数的结构入手：φ(x)的表达式是x乘以各个(1-1/p)的乘积（p是x的质因数）。要让φ(x)=n，x的质因数组合需要刚好把这些因子抵消后得到n。当n的质因数分解包含很多小质数时，能组合出的x的数量会显著增加，而这种情况下n的规模和N(n)的关系就对应了上面的渐近阶。

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