二次剩余

贡献者： int256

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

定义 1　伴随数

　　若 $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)$ 的解的情况，就是二次剩余。

定义 2　二次剩余

　　若 $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

。

定义 3　二次非剩余

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

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。

二次剩余

定义 1 伴随数

定义 2 二次剩余

定义 3 二次非剩余

定义 1　伴随数

定义 2　二次剩余

定义 3　二次非剩余