二次剩余

贡献者： int256

预备知识　素数与合数，整除

　　若 $p$ 是一个奇素数，且 $p ⧸ ∣ a$ ，而 $x$ 是 $1, 2, \dots, (p - 1)$ 中的一个，则根据定理 2 ，在

\begin{matrix} (1) & 1 \cdot x, 2 \cdot x, \dots, (p - 1) \cdot x \end{matrix}

这些数中，必有且仅有一个与

a

模

p

同余，这就说明，存在唯一的

x^{'}

使得

\begin{matrix} (2) & x x^{'} \equiv a (\mod p), \end{matrix}

称

x^{'}

是

x

关于

a

的伴随数（associate）。

　　我们会发现，由于伴随数的定义，要么会至少有一个 $x$ 与自己相伴，要么没有这样的 $x$ 。由此引出了 $x^{2} \equiv a (\mod p)$ 的解的情况，就是二次剩余。

　　若 $x_{1}$ 与自己关于 $a$ 在模奇素数 $p$ 意义下相伴，此时同余方程

\begin{matrix} (3) & x^{2} \equiv a (\mod p) \end{matrix}

有解

x = x_{1}

，就说

a

是

p

的二次剩余（quadratic residue），或简称为

p

的剩余，并记作

a R p

。

　　若不存在任何的 $x$ 与自己相伴，此时称 $a$ 是 $p$ 的二次非剩余（quadratic non-residue），或简称 $p$ 的非剩余，记作 $a N p$ 。