高次剩余

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

相关条目