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

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

从而转化为一个模
意义下的线性不定方程问题。
Euler 判别准则
在模
存在原根,即
为
或
时,欧拉判别法用于判别一个数模
是否为
次剩余。
定义
在模
存在原根时,对于模
缩剩余系中的
,当且仅当

时,
是模
的
次剩余。
在原根的视角下欧拉判别法是显然的,这里对最常用的情形,奇素数的二次剩余,进行详细说明。
奇素数的二次剩余
借助二次剩余符号,对于奇素数
和
有

证明
引理:令
为素数和模
意义下原根
并令
。那么
有解当且仅当
为偶数。
引理的证明:(充分性)假设
有解为
对于某个
成立。那么
。因此
(Fermat 小定理),而
为偶数,所以
为偶数。
(必要性)假设
为偶数,那么

而因为
为偶数,所以
为整数,因此
有解为
。
因为
为模
的原根,那么
的阶为
所以
且根据阶的定义,对于所有
满足
都有
,所以

考虑同余方程
。因为
且
对于某个
满足
成立。若同余方程存在解,则
为偶数,通过上述引理和 Fermat 小定理有

所以当
时解存在。
又因上述引理,
无解时
为奇数。假设
为奇数,那么

即得 Euler 判别准则,也可以推断出二次剩余符号为完全积性函数。
-1 与 k 次剩余
欧拉判别法的直接推论是,在模
存在原根,即
为
或
时,判断
是否为模
的
次剩余。
根据欧拉判别法,当且仅当

时,
是模
的
次剩余,即等价于

是偶数。
对于奇素数
的二次剩余情形,则有结论:

因此,当且仅当
为
型奇素数时,
是模
的二次剩余。当且仅当
为
型奇素数时,
是模
的二次非剩余。
单位根
定义
考虑方程:

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

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

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

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

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

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

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

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

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

于是
次剩余和
次单位根恰好构成了互补的概念:
一个数
是
次剩余,等价于
是
次剩余,等价于
是
次单位根。
一个数
是
次单位根,等价于
是
次单位根,等价于
是
次剩余。
接下来对于最常用的情形,奇素数的二次剩余,进行详细说明。
二次剩余和二次非剩余的数量
对于奇素数
和集合
,在模
意义下二次剩余的数量等于二次非剩余的数量。
证明
引理:对于
和奇素数
,
恰有
个解。
引理的证明:根据 Fermat 小定理,当
时有
。因此对于每个
,
是
的解。通过因式分解
有

其中
。根据 Lagrange 定理 我们知道
最多有
个解。因为
有
个解,所以显然
至少有
个解。如果只考虑
,我们知道最多有
个解。所以
恰有
个解。
根据 Euler 判别准则,对于
显然
,又因上述引理所以
有
个解,而集合中有
个元素,所以也有
个二次非剩余。
本页面最近更新:2023/5/27 22:46:55,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:ChungZH, Great-designer, iamtwz, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用