对奇素数 pp 和整数 aa，定义 Legendre 符号如下：
(ap)={0,p∣a,1,(p∤a)∧((∃x∈Z), a≡x2(modp)),−1,otherwise.\left(\frac{a}{p}\right)=\begin{cases} 0, & p\mid a,\\ 1, & (p\nmid a) \land ((\exists x\in\mathbf{Z}),~~a\equiv x^2\pmod p),\\ -1, & \text{otherwise}.\\ \end{cases}
Legendre 符号可进一步推广为 Jacobi 符号，Jacobi 符号可进一步推广为 Kronecker 符号。
Legendre 符号的性质
相等性质
a1≡a2(modp) ⟺ (a1p)=(a2p)a_1\equiv a_2\pmod p\iff \left(\dfrac{a_1}{p}\right)=\left(\dfrac{a_2}{p}\right)
完全积性
对任意整数 a1,a2a_1,a_2，
(a1a2p)=(a1p)(a2p)\left(\frac{a_1a_2}{p}\right)=\left(\frac{a_1}{p}\right)\left(\frac{a_2}{p}\right)
推论：对整数 a,ba,b，p∤bp\nmid b 有
(ab2p)=(ap)\left(\frac{ab^2}{p}\right)=\left(\frac{a}{p}\right)
参考
https://oi-wiki.org/math/number-theory/quad-residue/#legendre-符号