跳转到内容

高次剩馀

维基百科,自由的百科全书

数论中,模正整数次剩馀为正整数),即某整数次方数除以的馀数。以下讨论是奇质数,且馀数不为零的情况。

给定,若对某个,有成立时,则称次剩馀(英语:n-tic residue mod p)。

否则,对任意,都有,此时称次非剩馀(英语:n-tic non-residue mod p)。

次剩馀有类似于二次剩馀欧拉判别法的判别法如下: 若是奇质数不能整除,且(即整除),则是模次剩馀的充要条件为:

且若上式有解时,解数为

不能整除,则是模次剩馀的充要条件为:

其中最大公因数。同样上式有解时解数为

两个次剩馀相乘仍然是次剩馀,次剩馀和次非剩馀相乘为次非剩馀,但是与二次剩馀不同,当两个次非剩馀相乘时,并不一定是次剩馀。

对于二次剩馀)的状况,可以透过计算勒让德符号来确定,但是当高斯企图对于任意寻找类似算法时(高斯考虑了的情况),却找不到类似的算法,高次剩馀在某些方面的不规则是一个极困难的问题。

相关条目