高次剩餘

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

給定，若對某個，有成立時，則稱為模的次剩餘（）。

否則，對任意，都有，此時稱為模的次非剩餘（）。

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

。

且若上式有解時，解數為。

若不能整除，則是模的次剩餘的充要條件為：

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

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

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

 相關條目 
二次剩餘
三次互反律

Category:同余