剩余

模运算下的剩余问题，是将开方运算引入模运算的尝试。

令整数 $k \geq 2$ ，整数 $a$ ， $m$ 满足 $(a, m) = 1$ ，若存在整数 $x$ 使得

\begin{matrix} (1) & x^{k} \equiv a (\mod m) \end{matrix}

则称 $a$ 为模 $m$ 的 $k$ 次剩余，否则称 $a$ 为模 $m$ 的 $k$ 次非剩余。

二次剩余即是 $k$ 次剩余的特例。

当整数 $k \geq 2$ ，整数 $a$ ， $m$ 满足 $(a, m) = 1$ ，模 $m$ 有原根 $g$ 时，令 $d = (k, φ (m))$ ，则：

$a$ 为模 $m$ 的 $k$ 次剩余当且仅当 $d ∣ {ind}_{g} a$ ，即：
$a^{\frac{φ (m)}{d}} \equiv 1 (\mod m)$
方程 $(1)$ 若有解，则模 $m$ 下恰有 $d$ 个解
模 $m$ 的 $k$ 次剩余类的个数为 $\frac{φ (m)}{d}$ , 其有形式
$a \equiv g^{d i} (\mod m), (0 \leq i < \frac{φ (m)}{d})$

证明

令 $x = g^{y}$ ，则方程 $(1)$ 等价于
$g^{k y} \equiv g^{{ind}_{g} a} (\mod m)$
其等价于
$\begin{matrix} (2) & k y \equiv {ind}_{g} a (\mod φ (m)) \end{matrix}$
由同余的性质，我们知道 $y$ 有整数解当且仅当 $d = (k, φ (m)) ∣ {ind}_{g} a$ ，进而
$\begin{aligned} a^{\frac{φ (m)}{d}} \equiv 1 (\mod m) & ⟺ g^{\frac{φ (m)}{d} {ind}_{g} a} \equiv 1 (\mod m) \\ ⟺ φ (m) ∣ \frac{φ (m)}{d} {ind}_{g} a \\ ⟺ φ (m) d ∣ φ (m) {ind}_{g} a \\ ⟺ d ∣ {ind}_{g} a \end{aligned}$
当 $d ∣ {ind}_{g} a$ 时，由同余的性质可知方程 $(2)$ 模 $φ (m)$ 下恰有 $d$ 个解，进而方程 $(1)$ 模 $m$ 下恰有 $d$ 个解。
由 1 知 $a$ 为模 $m$ 的 $k$ 次剩余当且仅当 $d ∣ {ind}_{g} a$ ，故
${ind}_{g} a \equiv d i (\mod φ (m)), (0 \leq i < \frac{φ (m)}{d})$
故模 $m$ 的 $k$ 次剩余共有 $\frac{φ (m)}{d}$ 个同余类：
$a \equiv g^{d i} (\mod m), (0 \leq i < \frac{φ (m)}{d})$

参考资料

本页面最近更新：2025/8/1 01:37:06，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用