令整数 aa，pp 满足 (a,p)=1(a,p)=1，若存在整数 xx 使得
x2≡a(modp)x^2\equiv a\pmod p
则称 aa 为模 pp 的二次剩余，否则称 aa 为模 pp 的二次非剩余。
通俗一些，可以认为是求模意义下的 开平方 运算。对于更高次方的开方可参见 高次剩余。
勒让德符号
对奇素数 pp 和整数 aa，定义勒让德符号如下：
(ap)={0,p∣a,1,a 是模 p 的二次剩余,−1,a 不是模 p 的二次剩余.\left(\frac{a}{p}\right)=\begin{cases} 0, & p\mid a,\\ 1, & a \text{ 是模 } p \text{ 的二次剩余},\\ -1, & a\text{ 不是模 } p \text{ 的二次剩余}.\\ \end{cases}
判断二次剩余（计算勒让德符号）
欧拉判别法
对任意整数 aa，
ap−12≡(ap)(modp)a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)\pmod p
计算 1 和 -1 的二次剩余
- (1p)=1 \left(\dfrac{1}{p}\right)=1
- (−1p)=(−1)p−12={1,p≡1(mod4),−1,p≡3(mod4). \begin{aligned} \left(\dfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}} =\begin{cases} 1, & p\equiv 1\pmod 4,\\ -1, & p\equiv 3\pmod 4. \end{cases} \end{aligned}
由欧拉判别法易得.
高斯引理
设 (n,p)=1(n,p)=1, 对整数 k (1≤k≤p−12)k~\left(1\leq k\leq \dfrac{p-1}{2}\right)，令 rkr_k 为 nknk 模 pp 的最小非负剩余，设 mm 为所有 rkr_k 中大于 p2\dfrac{p}{2} 的个数，则
(np)=(−1)m\left(\frac{n}{p}\right)=(-1)^m
计算 2 的二次剩余
对奇素数 pp，
(2p)=(−1)p2−18={1,p≡±1(mod8)−1,p≡±3(mod8)\begin{aligned} \left(\frac{2}{p}\right)&=(-1)^{\frac{p^2-1}{8}}\\ &=\begin{cases} 1, & p\equiv \pm 1\pmod 8 \\ -1, & p\equiv \pm 3\pmod 8 \\ \end{cases} \end{aligned}
证明见高斯引理.
二次互反律
设 pp，qq 是两个不同的奇素数，则
(pq)=(qp)(−1)p−12q−12\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)(-1)^{\frac{p-1}{2}\frac{q-1}{2}}
二次剩余的数量
对于奇素数 pp，模 pp 意义下二次剩余和二次非剩余均有 p−12\frac{p-1}{2} 个。
证明
根据欧拉判别法，考虑 ap−12≡1(modp)a^{\frac{p-1}{2}}\equiv 1\pmod p.
注意到 p−12∣(p−1)\frac{p-1}{2}\mid (p-1)，由同余方程的定理可知 ap−12≡1(modp)a^{\frac{p-1}{2}}\equiv 1\pmod p 有 p−12\frac{p-1}{2} 个解。所以模 pp 意义下二次剩余和二次非剩余均有 p−12\frac{p-1}{2} 个。