一、定义

设p是一个奇素数，a是一个整数，且$ gcd(a,p)=1 $

如果存在整数x，使得同余方程$ x^2\equiv a(\mod p) $有解，则称a是模p的二次剩余

二、重要性质

1.数量分布

对于奇素数p，在1到p-1这p-1个整数中

恰好有$ \frac{p-1}{2} $个二次剩余

恰好有$ \frac{p-1}{2} $个非二次剩余

2.乘法封闭性

$ 二次剩余\times 二次剩余 \equiv 二次剩余 $

$ 二次非剩余\times 二次非剩余 \equiv 二次剩余 $

$ 二次剩余\times 二次非剩余 \equiv 二次非剩余 $

三、勒让德符号（Legendre Symbol）

为了方便表示和计算，数学及引入了勒让德符号$ (\frac{a}{p}) $，定义如下：

$ (\frac{a}{p})=\begin{cases}1; 若a是模p的二次剩余\-1; 若a是模p的二次非剩余\0; 若a\equiv 0(\mod p)\end{cases} $

勒让德符号具有完全积性：$ (\frac{ab}{p})=(\frac{a}{p})(\frac{b}{p}) $

四、欧拉判别法（Euler’s Criterion）

使用欧拉判别法可以快速判断一个数a是否为模p的二次剩余

对于奇素数p和整数a（$ p\nmid a $）

$ (\frac{a}{p})\equiv a^{\frac{p-1}{2}}(\mod p) $

如果计算结果$ a^{\frac{p-1}{2}}\equiv 1(\mod p) $，则a是二次剩余

如果计算结果$ a^{\frac{p-1}{2}}\equiv -1(\mod p) $，则a是二次非剩余

原文链接：https://www.yuque.com/fragrantveget/ucxpnh/yogb9vgvqg7kygdf?singleDoc# 《二次剩余（Quadratic Residue）》