跳至內容

高次剩餘

維基百科,自由的百科全書

數論中,模正整數次剩餘為正整數),即某整數次方數除以的餘數。以下討論是奇質數,且餘數不為零的情況。

給定,若對某個,有成立時,則稱次剩餘(英語:n-tic residue mod p)。

否則,對任意,都有,此時稱次非剩餘(英語:n-tic non-residue mod p)。

次剩餘有類似於二次剩餘歐拉判別法的判別法如下: 若是奇質數不能整除,且(即整除),則是模次剩餘的充要條件為:

且若上式有解時,解數為

不能整除,則是模次剩餘的充要條件為:

其中最大公因數。同樣上式有解時解數為

兩個次剩餘相乘仍然是次剩餘,次剩餘和次非剩餘相乘為次非剩餘,但是與二次剩餘不同,當兩個次非剩餘相乘時,並不一定是次剩餘。

對於二次剩餘)的狀況,可以透過計算勒讓德符號來確定,但是當高斯企圖對於任意尋找類似算法時(高斯考慮了的情況),卻找不到類似的算法,高次剩餘在某些方面的不規則是一個極困難的問題。

相關條目