高次同余方程

高次同余方程研究 $x^k\equiv a\pmod p$ 的可解性：二次情形即二次剩余，一般情形借助原根与离散对数化为线性同余。

幂同余的可解性

设 $p$ 为奇素数，$p\nmid a$，固定模 $p$ 的原根 $g$，令 $a\equiv g^t\pmod p$。方程

$$x^k\equiv a\pmod p$$

等价于 $ku\equiv t\pmod{p-1}$（令 $x=g^u$），故有解当且仅当

$$d=\gcd(k,p-1)\mid t$$

此时恰有 $d$ 个解：$u\equiv u_0+\dfrac{p-1}{d}j\pmod{p-1}$，$j=0,1,\dots,d-1$。

可解性准则

$x^k\equiv a\pmod p$ 可解当且仅当

$$a^{(p-1)/d}\equiv1\pmod p,\qquad d=\gcd(k,p-1)$$

（由 $a^{(p-1)/d}\equiv g^{t(p-1)/d}\pmod p$ 与 $d\mid t$ 的等价性看出）。

一般模

• 二次情形（$k=2$）由勒让德符号与二次互反律判定（见二次剩余）
• 对一般模 $m$，中国剩余定理把 $x^k\equiv a\pmod m$ 化归为素数幂模；模 $p^e$ 的解可由模 $p$ 的解经 Hensel 引理提升

示例

• $x^3\equiv2\pmod7$：$g=3$，$2\equiv3^2$，$d=\gcd(3,6)=3\nmid2$，无解（模 $7$ 的立方剩余为 $\{1,6\}$，不含 $2$）
• $x^3\equiv6\pmod7$：$6\equiv3^3$，$d=3\mid3$，解 $u\equiv1+2j$，即 $x\equiv3,5,6\pmod7$（$3^3\equiv6$，$5^3\equiv6$，$6^3\equiv6$）