> For the complete documentation index, see [llms.txt](https://chenyangwang.gitbook.io/mathematical-base-for-information-safety/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chenyangwang.gitbook.io/mathematical-base-for-information-safety/er-ci-tong-yu-shi-he-ping-fang-sheng-yu/lengendre-fu-hao.md).

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