剩余与单位根

剩余

模运算下的剩余问题，是将开方运算引入模运算的尝试。在复数中引入开方运算借助了多值的对数函数，在剩余问题中也可以借助离散对数来方便理解与讨论。

定义

一个数 ，如果与 互素，且模 同余于某个数的 次方，则称 为模 的 次剩余（residue）。一个不与 互素的数 ，不同余于任何数的 次方，则称 为模 的模 的 次非剩余。

解释

对 次剩余求解，也就是对常数 解下面的这个方程：

通俗一些，可以认为是求模意义下的开 次方运算。

当模 存在原根 的时候，两边取对数：

从而转化为一个模 意义下的线性不定方程问题。

单位根

定义

考虑方程：

根据拉格朗日定理，这样的解最多有 个。称全部解为模 意义下的 次单位根（the -th root of unity）。

解释

当模 存在原根 的时候，两边取对数：

同样转化为一个模 意义下的线性不定方程问题。这个方程始终有解 ，并且也可以构造其他形式的解。可以设：

那么，模 意义下的全体 次单位根可以表示为：

选定原根 之后，如果不加说明，一般叙述的 次单位根即为上述 ，其它解均可以用 的幂表示。

单位根的个数就是上述集合的元素个数。与复数中的单位根不同，由于取值是离散而有限的，单位根的个数最多为 个，不随 的增加而无限增加。根据全体 次单位根的表达式写法，可以得到全体 次单位根的个数为：

可见，如果 与 互素，则只有 是单位根。单位根的个数必然为 的约数，并且全体 个数均为 次单位根。

性质

单位根有三个重要的性质。对于任意正整数 和整数 ：

推导留给读者自证。这三个性质在快速数论变换中会得到应用。但要注意，后两条仅当 与 不相等，即 次单位根个数比 次单位根个数多时才成立。

本原单位根

模 意义下的 次单位根特指 ，是为了在应用时方便。

在解方程的视角看来，满足 性质的不止 一个，对于 的若干次幂也会满足类似的性质。

虽然这里的本原单位根与复数中的本原单位根表达的含义一致，性质的应用一致，但是由于这里的本原单位根取值离散而有限，并且每个数都是 次单位根，这里本原单位根的定义方法与复数中的本原单位根定义方法不同。

这种定义方法与阶的概念完全一致：

定义

一个数 模 的阶是 ，等价于 是模 的 次本原单位根。

如果一个数 是 次单位根，并且对于任意大于 小于 的 ， 不是 次单位根，则 是 次本原单位根。

解释

由于阶的定义是唯一的，一个数 只有一个固定的阶，不同次数的本原单位根集合交集为空。

与复数中的本原单位根一致，如果存在 次本原单位根，借助任意一个 次本原单位根，都可以生成全体 次单位根。此时，全体 次单位根恰好为，对于全体 的约数 ，全体 次本原单位根集合的并集。

由于所有的数均为 次单位根，因此当 比 大的时候，不存在 次本原单位根。当且仅当 整除 的时候，存在 次本原单位根。

当 次本原单位根存在时，全体 次本原单位根的个数为 。此时全体 次本原单位根恰好为：

与复数中的本原单位根一致。

对于一般的 ，需要将 替换为 。由于 是 的约数，进行替换之后则将问题转化为已讨论的情形。

剩余方程的解

借助单位根的概念可以很好地研究当原根 存在时，剩余方程

的全体解，即与它等价的取对数之后的方程

的全体解。

当剩余方程存在一个解 的时候，方程的全体解恰好为 乘上全体 次单位根，因此个数恰好为单位根的个数 。因此，只要 是 次剩余，方程的解数即为 。

问题转化为剩余方程有解或无解的条件。根据裴蜀定理，当且仅当 整除 时，方程有解，其余情形方程无解。

因此，全体 次剩余共有 个，分别为

于是 次剩余和 次单位根恰好构成了互补的概念：

一个数 是 次剩余，等价于 是 次剩余，等价于 是 次单位根。

一个数 是 次单位根，等价于 是 次单位根，等价于 是 次剩余。

本页面最近更新：2022/9/18 20:58:01，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：ChungZH, Great-designer, iamtwz, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用