如何求解欧拉函数方程φ(n)=78？

先从你提到的简单情况说起：

• 素数解：素数p的欧拉函数φ(p)=p-1，所以当p-1=78时，p=79，这是第一个解，79确实是素数，没问题。
• n=158的验证：158=2×79，因为欧拉函数是积性函数（两个互质数相乘的欧拉函数等于各自欧拉函数的乘积），所以φ(158)=φ(2)×φ(79)=1×78=78，这个解释比你之前说的更直接准确，不用纠结不互质的数，直接用积性性质就够了。

接下来我们用欧拉函数的通用公式系统找所有解。欧拉函数的公式是：
若$n=\displaystyle \prod_{i=1}^k p_i^{\alpha_i}$（$p_i$是不同素数，$\alpha_i≥1$），则$\phi(n) = \displaystyle \prod_{i=1}^k p_i^{\alpha_i-1} (p_i-1)$

首先把78分解质因数：$78=2×3×13$，我们需要把78拆分成若干个形如$p^{\alpha-1}(p-1)$的因子相乘，每个因子对应n的一个素因子幂，且这些素因子互不相同。

情况1：n是素数幂$p^\alpha$ #

此时$\phi(n)=p^{\alpha-1}(p-1)=78$：

• 当$\alpha=1$时，$p-1=78$，解得$p=79$（素数），这就是我们找到的第一个解。
• 当$\alpha≥2$时，$p^{\alpha-1}$必须整除78，78的素因子只有2、3、13：
  • 试$p=2$：$2^{{\alpha-1}(2-1)=2}{\alpha-1}=78$，78不是2的幂，无解；
  • 试$p=3$：$3^{{\alpha-1}(3-1)=2×3}{\alpha-1}=78$，得$3^{\alpha-1}=39$，39不是3的幂，无解；
  • 试$p=13$：$13^{{\alpha-1}(13-1)=12×13}{\alpha-1}=78$，得$13^{\alpha-1}=6.5$，不是整数，无解。
    所以素数幂的情况只有$n=79$。

情况2：n有两个不同的素因子（$n=p^\alpha q^\beta$，$\alpha,\beta≥1$） #

此时$\phi(n)=p^{{\alpha-1}(p-1)×q}{\beta-1}(q-1)=78$，我们把78拆成两个因子的所有组合来试：

• 组合1：$2×39$
  • 因子2可以对应：要么$p=3$（$\alpha=1$，$\phi(3)=2$），要么$p=4$（$\alpha=2$，$\phi(4)=2$）；
  • 因子39需要对应某个素数幂的欧拉函数：$\phi(q^\beta)=39$，但39=3×13，若$\beta=1$则$q-1=39→q=40$（非素数）；若$\beta≥2$，$q$只能是3或13，但计算后都得不到39，所以这个组合无解。
• 组合2：$3×26$
  • 因子3找不到对应的素数幂：$\phi(p^{\alpha)=3$的话，$\alpha=1$时$p-1=3→p=4$（非素数）；$\alpha≥2$时试$p=3$，$2×3}{\alpha-1}=3$，结果不是整数，无解。
• 组合3：$6×13$
  • 因子6可以对应$p=7$（$\alpha=1$，$\phi(7)=6$）或$p=9$（$\alpha=2$，$\phi(9)=6$）；
  • 因子13找不到对应的素数幂：$\phi(q^{\beta)=13$的话，$\beta=1$时$q-1=13→q=14$（非素数）；$\beta≥2$时试$q=13$，$12×13}{\beta-1}=13$，结果不是整数，无解。
• 其他组合（$13×6$、$26×3$、$39×2$）要么第一个因子找不到对应素数幂，要么第二个因子无解，所以两个素因子的情况只有你提到的$n=2×79=158$（对应$\phi(2)×\phi(79)=1×78=78$）。

情况3：n有三个或更多不同素因子 #

78只有3个质因子，若n有3个不同素因子，那么$\phi(n)$需要拆成3个形如$p^{\alpha-1}(p-1)$的因子相乘：

• 比如拆成$2×3×13$，但$\phi(p^{\alpha)=3$和$\phi(p}\alpha)=13$都找不到对应的素数幂（前面已经验证过）；
• 若n有4个或更多素因子，$\phi(n)$至少是$(2-1)(3-1)(5-1)(7-1)=48$，但拆成4个因子的话，必须有一个因子对应$\phi(p^{\alpha)=1$（即$p=2$），剩下的因子需要凑出78，但$\phi(q}\beta)=3$和$\phi(r^\gamma)=13$都无解，所以这种情况也没有解。

最终所有解 #

经过完整分析，满足$\phi(n)=78$的n只有两个：79和158。

内容的提问来源于stack exchange，提问作者i dont know much about algebra