Lengendre符号

定义

$p$为素数

\left(\frac{a}{p}\right)=\left\{ \begin{array}{**lr**} 1 &a为模p的平方剩余\\ -1 &a为模p的非平方剩余\\ 0 &p\mid a \end{array} \right.

欧拉判别法则

$p$为奇素数，对整数$a$

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

性质

• $\left(\frac{1}{p}\right)=1$
• $\left(\frac{-1}{p}\right)={\left(-1\right)}^{\frac{p-1}{2}}$
• $p$为奇素数，则

  • $\left(\frac{a+p}{p}\right)=\left(\frac{a}{p}\right)$
  • $\left(\frac{a\cdot b}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$
  • 设$\left(a,p\right)=1$，则$\left(\frac{a^2}{p}\right)=1$

高斯引理

$p$为奇素数，$a$为整数，$\left(a,p\right)=1$，整数$a\cdot1,a\cdot2,\cdots,a\cdot\frac{p-1}{2}$中模$p$的最小正剩余大于$\frac{p}{2}$的个数是$m$，则$\left(\frac{a}{p}\right)={\left(-1\right)}^m$