高次剩餘

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

給定d，若對某個X，有X^n \equiv d \pmod{p}成立時，則稱d為模p的n次剩餘（）。

否則，對任意X，都有X^n \not\equiv d \pmod{p}，此時稱d為模p的n次非剩餘（）。

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

:d^{\frac{p-1}{n}} \equiv 1 \pmod{p}。

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

若n不能整除p-1，則d是模p的n次剩餘的充要條件為：

:d^{\frac{p-1}{k}} \equiv 1 \pmod{p},
其中k為最大公因數(n,p-1)。同樣上式有解時解數為k。

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

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

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