K 次剩餘

我们借助原根与指数来讨论高次同余方程，在目前高次同余方程的求解依旧没有简便可行的通法，这里仅介绍最简单的高次方程，并研究其可解性。

k 次剩余的概念

设$k \geqslant 2$，$(a, m) = 1$，如果同余方程

$$x^k \equiv a \pmod{m}$$

有整数解，就称$a$是$m$的$k$次剩余，否则称$a$是$m$的$k$次非剩余。

理论结果

当$m$有原根$g$时，$a$是$m$的$k$次剩余当且仅当$a^{\frac{\varphi(m)}{(k, \varphi(m))}} \equiv 1 \pmod{m}$，在有解时模$m$的解数为$(k, \varphi(m))$；

模$m$的$k$次剩余类的个数为$\dfrac{\varphi(m)}{(k, \varphi(m))}$，它们是$a \equiv g^{ i (k, \varphi(m))}, 0 \leqslant i \leqslant \dfrac{\varphi(m)}{(k, \varphi(m))} - 1.$

示例

例1. 解方程$x^8 \equiv 3 \pmod{11}.$
例2. 解方程$7 \cdot 3^x \equiv 6 \pmod{11}.$

上下节

• 上一节：指数
• 下一节：二次剩余