剩余

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

令整数 $k\geq 2$ ，整数，满足，若存在整数使得

x^k\equiv a\pmod m\tag{1}

则称为模的次剩余，否则称为模的次非剩余。

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

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

为模的次剩余当且仅当 $d\mid \operatorname{ind}_g a$ ，即：
$a^{\frac{\varphi(m)}{d}}\equiv 1\pmod m$
方程若有解，则模下恰有个解
模的次剩余类的个数为 $\dfrac{\varphi(m)}{d}$ , 其有形式
$a\equiv g^{di}\pmod m,\qquad \left(0\leq i<\frac{\varphi(m)}{d}\right)$

证明

令，则方程等价于
$g^{ky}\equiv g^{\operatorname{ind}_g a}\pmod m$
其等价于
$ky\equiv \operatorname{ind}_g a\pmod{\varphi(m)}\tag{2}$
由同余的性质，我们知道有整数解当且仅当 $d=(k,\varphi(m))\mid \operatorname{ind}_g a$ ，进而
$\begin{aligned} a^{\frac{\varphi(m)}{d}}\equiv 1\pmod m&\iff g^{\frac{\varphi(m)}{d}\operatorname{ind}_g a}\equiv 1\pmod m\\ &\iff \varphi(m)\mid\frac{\varphi(m)}{d}\operatorname{ind}_g a\\ &\iff \varphi(m)d\mid \varphi(m)\operatorname{ind}_g a\\ &\iff d\mid \operatorname{ind}_g a\\ \end{aligned}$
当 $d\mid \operatorname{ind}_g a$ 时，由同余的性质可知方程模 $\varphi(m)$ 下恰有个解，进而方程模下恰有个解。
由 1 知为模的次剩余当且仅当 $d\mid \operatorname{ind}_g a$ ，故
$\operatorname{ind}_g a\equiv di\pmod{\varphi(m)},\qquad \left(0\leq i<\frac{\varphi(m)}{d}\right)$
故模的次剩余共有 $\dfrac{\varphi(m)}{d}$ 个同余类：
$a\equiv g^{di}\pmod m,\qquad \left(0\leq i<\frac{\varphi(m)}{d}\right)$

参考资料