高次剩馀

数论中，模正整数 $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$ 的情况），却找不到类似的算法，高次剩馀在某些方面的不规则是一个极困难的问题。

相关条目