高次剩餘

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

給定 $d$ ，若對某個 $X$ ，有 $X^{n} \equiv d (\mod p)$ 成立時，則稱 $d$ 為模 $p$ 的 $n$ 次剩餘（Template:Lang-en）。

否則，對任意 $X$ ，都有 $X^{n} \equiv̸ d (\mod p)$ ，此時稱 $d$ 為模 $p$ 的 $n$ 次非剩餘（Template:Lang-en）。

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

d^{\frac{p - 1}{n}} \equiv 1 (\mod p)

。

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

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

d^{\frac{p - 1}{k}} \equiv 1 (\mod p),

其中 $k$ 為最大公因數 $(n, p - 1)$ 。同樣上式有解時解數為 $k$ 。

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

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

相關條目