高次剩餘

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

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

否則，對任意 $X$ ，都有 $X^{n}\not \equiv d{\pmod {p}}$ ，此時稱 $d$ 為模 $p$ 的 $n$ 次非剩餘（英語：n-tic non-residue mod p）。

$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\geq 3$ 尋找類似算法時（高斯考慮了 $n=3$ 和 $n=4$ 的情況），卻找不到類似的算法，高次剩餘在某些方面的不規則是一個極困難的問題。

相關條目