高次剩餘

高次剩餘意即對於任意的整數${\displaystyle X}$ 的${\displaystyle n}$ 次方數${\displaystyle X^{n}}$ (${\displaystyle n}$ 為正整數)除以任意正整數${\displaystyle m}$ 所餘的數${\displaystyle d}$ ，我們稱此${\displaystyle d}$ 為"模${\displaystyle m}$ 的${\displaystyle n}$ 次剩餘"，以下討論n是質數的情況(且此質數為奇質數，以下${\displaystyle m=p}$ 且${\displaystyle p}$ 不能整除${\displaystyle d}$ )：

當對於某個${\displaystyle d}$ 及某個${\displaystyle X}$ ，${\displaystyle X^{n}\equiv d{\pmod {p}}}$ 此式成立時，稱「${\displaystyle d}$ 是模${\displaystyle p}$ 的${\displaystyle n}$ 次剩餘」

當對於某個${\displaystyle d}$ 及某個${\displaystyle X}$ ，${\displaystyle X^{n}\equiv d{\pmod {p}}}$ 此式不成立時，稱「${\displaystyle d}$ 是模${\displaystyle p}$ 的${\displaystyle n}$ 非次剩餘」

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

${\displaystyle d^{\frac {p-1}{n}}\equiv 1{\pmod {p}}}$

且有解時，解數為${\displaystyle n}$

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

${\displaystyle d^{\frac {p-1}{k}}\equiv 1{\pmod {p}}}$ ，其中${\displaystyle k=(n,p-1)}$ ，且有解時解數為${\displaystyle k}$

兩個n次剩餘相乘猶然是${\displaystyle n}$ 次剩餘，${\displaystyle n}$ 次剩餘和${\displaystyle n}$ 次非剩餘相乘為${\displaystyle n}$ 次非剩餘，但是當兩個${\displaystyle n}$ 次非剩餘相乘時，並不一定是${\displaystyle n}$ 次剩餘

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

相關條目

二次剩餘