剩余

剩余

前置知识：离散对数

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

定义

令整数 ，整数 ， 满足 ，若存在整数 使得

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

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

性质

当整数 ，整数 ， 满足 ，模 有原根 时，令 ，则：

1. 为模 的 次剩余当且仅当 ，即：

2. 方程 若有解，则模 下恰有 个解

3. 模 的 次剩余类的个数为 , 其有形式

证明

1. 令 ，则方程 等价于

   其等价于

   由同余的性质，我们知道 有整数解当且仅当 ，进而

2. 当 时，由同余的性质可知方程 模 下恰有 个解，进而方程 模 下恰有 个解。

3. 由 1 知 为模 的 次剩余当且仅当 ，故

   故模 的 次剩余共有 个同余类：

参考资料

1. 冯克勤。初等数论及其应用。

---

最后更新: 2023年7月23日
创建日期: 2022年8月21日