高次剩余

数论中，模正整数${\displaystyle m}$的${\displaystyle n}$次剩余（${\displaystyle n}$为正整数），即某整数${\displaystyle X}$的${\displaystyle n}$次方数${\displaystyle X^{n}}$除以${\displaystyle m}$的余数。以下讨论${\displaystyle m}$是奇质数${\displaystyle p}$，且余数${\displaystyle d}$不为零的情况。

给定${\displaystyle d}$，若对某个${\displaystyle X}$，有${\displaystyle X^{n}\equiv d{\pmod {p}}}$成立时，则称${\displaystyle d}$为模${\displaystyle p}$的${\displaystyle n}$次剩余（英语：n-tic residue mod p）。

否则，对任意${\displaystyle X}$，都有${\displaystyle X^{n}\not \equiv d{\pmod {p}}}$，此时称${\displaystyle d}$为模${\displaystyle p}$的${\displaystyle n}$次非剩余（英语：n-tic non-residue mod p）。

${\displaystyle n}$次剩余有类似于二次剩余欧拉判别法的判别法如下： 若${\displaystyle p}$是奇质数，${\displaystyle p}$不能整除${\displaystyle d}$，且${\displaystyle n|p-1}$（即${\displaystyle n}$能整除${\displaystyle p-1}$），则${\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}$为最大公因数${\displaystyle (n,p-1)}$。同样上式有解时解数为${\displaystyle k}$。

两个${\displaystyle 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}$的情况），却找不到类似的算法，高次剩余在某些方面的不规则是一个极困难的问题。

相关条目

• 二次剩余
• 三次互反律
• 四次互反律（英语：quartic reciprocity）