剩余与单位根
剩余
模运算下的剩余问题,是将开方运算引入模运算的尝试。在复数中引入开方运算借助了多值的对数函数,在剩余问题中也可以借助离散对数来方便理解与讨论。
定义
一个数
,如果与
互素,且模
同余于某个数的
次方,则称
为模
的
次剩余(residue)。一个不与
互素的数
,不同余于任何数的
次方,则称
为模
的模
的
次非剩余。
解释
对
次剩余求解,也就是对常数
解下面的这个方程:

通俗一些,可以认为是求模意义下的开
次方运算。
当模
存在原根
的时候,两边取对数:

从而转化为一个模
意义下的线性不定方程问题。
单位根
定义
考虑方程:

根据拉格朗日定理,这样的解最多有
个。称全部解为模
意义下的
次单位根(the
-th root of unity)。
解释
当模
存在原根
的时候,两边取对数:

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

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

选定原根
之后,如果不加说明,一般叙述的
次单位根即为上述
,其它解均可以用
的幂表示。
单位根的个数就是上述集合的元素个数。与复数中的单位根不同,由于取值是离散而有限的,单位根的个数最多为
个,不随
的增加而无限增加。根据全体
次单位根的表达式写法,可以得到全体
次单位根的个数为:

可见,如果
与
互素,则只有
是单位根。单位根的个数必然为
的约数,并且全体
个数均为
次单位根。
性质
单位根有三个重要的性质。对于任意正整数
和整数
:

推导留给读者自证。这三个性质在快速数论变换中会得到应用。但要注意,后两条仅当
与
不相等,即
次单位根个数比
次单位根个数多时才成立。
本原单位根
模
意义下的
次单位根特指
,是为了在应用时方便。
在解方程的视角看来,满足
性质的不止
一个,对于
的若干次幂也会满足类似的性质。
虽然这里的本原单位根与复数中的本原单位根表达的含义一致,性质的应用一致,但是由于这里的本原单位根取值离散而有限,并且每个数都是
次单位根,这里本原单位根的定义方法与复数中的本原单位根定义方法不同。
这种定义方法与阶的概念完全一致:
定义
一个数
模
的阶是
,等价于
是模
的
次本原单位根。
如果一个数
是
次单位根,并且对于任意大于
小于
的
,
不是
次单位根,则
是
次本原单位根。
解释
由于阶的定义是唯一的,一个数
只有一个固定的阶,不同次数的本原单位根集合交集为空。
与复数中的本原单位根一致,如果存在
次本原单位根,借助任意一个
次本原单位根,都可以生成全体
次单位根。此时,全体
次单位根恰好为,对于全体
的约数
,全体
次本原单位根集合的并集。
由于所有的数均为
次单位根,因此当
比
大的时候,不存在
次本原单位根。当且仅当
整除
的时候,存在
次本原单位根。
当
次本原单位根存在时,全体
次本原单位根的个数为
。此时全体
次本原单位根恰好为:

与复数中的本原单位根一致。
对于一般的
,需要将
替换为
。由于
是
的约数,进行替换之后则将问题转化为已讨论的情形。
剩余方程的解
借助单位根的概念可以很好地研究当原根
存在时,剩余方程

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

的全体解。
当剩余方程存在一个解
的时候,方程的全体解恰好为
乘上全体
次单位根,因此个数恰好为单位根的个数
。因此,只要
是
次剩余,方程的解数即为
。
问题转化为剩余方程有解或无解的条件。根据裴蜀定理,当且仅当
整除
时,方程有解,其余情形方程无解。
因此,全体
次剩余共有
个,分别为

于是
次剩余和
次单位根恰好构成了互补的概念:
一个数
是
次剩余,等价于
是
次剩余,等价于
是
次单位根。
一个数
是
次单位根,等价于
是
次单位根,等价于
是
次剩余。
本页面最近更新:2022/9/18 20:58:01,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:ChungZH, Great-designer, iamtwz, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用