二次剩余
贡献者： int256
定义 1 伴随数
若 $p$ 是一个奇素数，且 $p \not{\mid}~ a$，而 $x$ 是 $1, 2, \dots, (p-1)$ 中的一个，则根据定理 2 ，在
\begin{equation}
1 \cdot x, 2 \cdot x, \dots, (p-1)\cdot x ~~
\end{equation}
这些数中，必有且仅有一个与 $a$ 模 $p$ 同余，这就说明，存在唯一的 $x'$ 使得
\begin{equation}
x x' \equiv a \pmod p ~,
\end{equation}
称 $x'$ 是 $x$ 关于 $a$ 的
伴随数（associate）。
我们会发现，由于伴随数的定义，要么会至少有一个 $x$ 与自己相伴，要么没有这样的 $x$。由此引出了 $x^2 \equiv a \pmod p$ 的解的情况，就是二次剩余。
定义 2 二次剩余
若 $x_1$ 与自己关于 $a$ 在模奇素数 $p$ 意义下相伴，此时同余方程
\begin{equation}
x^2 \equiv a \pmod p ~~
\end{equation}
有解 $x = x_1$，就说 $a$ 是 $p$ 的
二次剩余（quadratic residue），或简称为 $p$ 的
剩余，并记作 $a \operatorname {R} p$。
定义 3 二次非剩余
若不存在任何的 $x$ 与自己相伴，此时称 $a$ 是 $p$ 的二次非剩余（quadratic non-residue），或简称 $p$ 的非剩余，记作 $a \operatorname N p$。