- 下文中 \(g\) 代表当前模数的原根。
求 \(x^n\equiv k\pmod m\) 的解。
先对 \(m\) 分解成 \(\prod p_i^{q_i}\)，对每个 \(p_i^{q_i}\) 求出 \(x^n\equiv k\pmod m\) 的解，然后用中国剩余定理求出原方程的解。
考虑模数为 \(p_i^{q_i}\) 的解。经典的转化就是用原根把幂次变为乘法，即求出得到 \(l\) 使 \(g^l\equiv k \pmod m\)，求 \(xn\equiv k\pmod{\phi(m)}\)（扩展欧几里得算法），答案即为 \(g^x\)。
几个特殊情况：
- 如果 \(k\not\perp p_i^{q_i}\)，那么无法得到满足条件的 \(l\) 使得 \(g^l\equiv k\pmod p_i^{q_i}\)。
- 考虑到 \(2^c(c>2)\) 没有原根，所以要特殊处理。
推论
当 \(m\) 存在原根且 \(\gcd(k,m)=1\) 时，\(x^n\equiv k\pmod m\) 有解当且仅当 \(k^{\frac{\phi(m)}{\gcd(\phi(m),n)}}\equiv 1\pmod m\)。
充分性：若方程有解那么
必要性：若答案存在解 \(x=g^s\)，那么 \(g^{sn=l}\equiv k\)，一定满足 \(\gcd(n,\phi(m))|sn\bmod \phi(m)\)，如果不满足则无解。满足了那么 \(\phi(m)|\frac{l\phi(m)}{\gcd(\phi(m),n)}\)。
\(k\not\perp m\)
若 \(k=0\)，那么 \(p^{\lceil\frac{q}{n}\rceil}|x\)。
否则将 \(k\) 拆分成 \(up^t\)，其中 \(u\perp p\)，当 \(n|t\) 才有解，即求出 \(x\equiv u\pmod {p^{q-t}}\) 的解 \(x\)，答案为 \(xp^{\frac{t}{n}}\)。
可以知道化解完的答案个数为 \(\gcd(n, \phi(q^p))\)。
\(2^c(c>2)\)
\(x\equiv k\pmod {2^c}\)，利用上面的 \(k\not\perp 2^c\) 转化为 \(k\perp 2^c\)。
由于 \(2^c\) 没有原根但可以使用 \((-1)^a5^b(0\le a\le 1,0\le b< 2^{c-2})\) 表示，下面给出证明。
引理 \(1\)：\(5^{2^{c-3}}\equiv 2^{c-1}+1\pmod {2^c}\)
考虑归纳法，若 \(c=3\) 显然成立，那么 \(5^{2^{c-3}}\equiv 2^{c-1} + 1 \operatorname{or} 2^c + 2^{c-1} + 1\pmod {2^{c+1}}\)，两边同取平方，后面变为 \(2^{2(c-1)}+2^c+1\equiv2^c+1\) 和 \(2^{2c+1}+2^{2c-1}+2^{c+1}+2^c+1\equiv2^c+1\)。
引理 \(2\)：\(5\) 模 \(2^c\) 的阶为 \(2^{c-2}\)。
首先 \(5\) 的阶一定为 \(2^{c-1}\) 的因数，即 \(2^i\)，根据引理 \(1\)，\(i>c-3\)，引理 \(1\) 中两边取平方得到 \(5^{2^{c-2}}\equiv 1\pmod{2^c}\)，即 \(i\le c-2\)。
引理 \(3\)：\((-1)^a5^b(0\le a\le 1,0\le b< 2^{c-2})\) 互不相同
若 \((-1)^a5^b\equiv(-1)^c5^d\)，可知 \(a\not=c\)，那么 \(5^b+5^c\equiv 0\)，左边模 \(4\) 为 \(1\)，右边模 \(4\) 为 \(0\)，故不成立。
做法：那么就将 \((-1)^a\) 和 \(5^b\) 分开计算，计算方法和上面一样。