关于同余方程$x^a\equiv b \pmod {p^m}$解的存在性的疑问
嘿，我完全理解你自学数论的心情——非专业出身啃这个确实需要慢慢摸索，你的问题提得特别好！先聊聊你猜测的$(a,\phi(pm))=1$的情况：当这个条件满足时，**如果b和p互质**，那方程确实一定有解！因为此时a在模$\phi(pm)$下有逆元，假设逆元是k，那么$x = b^k \pmod {pm}$就是解，你可以验证一下：$(bk)^a = b^{ka} ≡ b^{1 + t\phi(p^m)} ≡ b \cdot (b{\phi(pm)})^t ≡ b \cdot 1^t ≡ b \pmod {pm}$，这里用到了欧拉定理（因为b和p互质，所以$b{\phi(p^m)}≡1 \pmod {p^m}$）。
不过解的存在性其实要分情况讨论，不是只有这一种场景：
情况1：b和p互质
这时候方程有解的充要条件是：$b{\phi(pm)/d} ≡ 1 \pmod {p^m}$，其中$d = \gcd(a, \phi(pm))$。你之前说的$(a,\phi(pm))=1$是这个条件的特例——此时d=1，$\phi(p^m)/d = \phi(p^m)$，欧拉定理直接满足这个同余式，所以一定有解。而且当解存在时，解的个数正好是d个。情况2：b是p的倍数（即p|b）
先设$b = p^k \cdot c$，其中c和p互质，k≥1。那方程$x^a ≡ p^k c \pmod {p^m}$有解的话，x必须是p的倍数，设$x = p^t \cdot y$（y和p互质），代入方程得：$p^{ta} y^a ≡ p^k c \pmod {p^m}$。
这时候要满足两个条件：- 首先k必须能被a整除（也就是ta=k，t=k/a），如果k不能被a整除，那ta要么大于k（左边是p的倍数，右边c和p互质，不可能相等），要么小于k（左边p的幂次不够，也无法匹配右边），都会导致无解。
- 当k能被a整除时，方程会简化为$y^a ≡ c \pmod {p^{m - k}}$，这就回到了情况1的问题，只要c满足情况1的充要条件，就有解。
举个简单例子帮你理解：比如方程$x^2 ≡ 4 \pmod {8}$，p=2，m=3，a=2，b=4=2²。k=2能被a=2整除，t=1，代入后得到$y^2 ≡1 \pmod {2}$，y取1或3（模2都等于1），对应x=2或6，确实是方程的解。再比如$x^2 ≡2 \pmod {8}$，b=2=2¹，k=1不能被a=2整除，所以无解，这也符合实际——平方数模8只能是0、1、4，确实没有2。
备注：内容来源于stack exchange，提问作者user286046
