Legendre 符号
| 勒让德符号 | |
|---|---|
| 术语名称 | 勒让德符号 |
| 英语名称 | Legendre symbol |
勒让德符号(Legendre symbol)是一个为便于某奇质数模的二次剩余情况而引入的符号，表征了对应二次同余方程是否有解。
定义
对奇质数 [math]\displaystyle{ p }[/math] ，对任意整数 [math]\displaystyle{ a }[/math] ，定义运算 [math]\displaystyle{ \left(\frac{a}{p}\right) = \begin{cases} 1 &, a \text{ 是模 } p \text{的二次剩余} \\ -1 &, a \text{ 是模 } p \text{的二次非剩余} \\ 0 &, p \mid a \\ \end{cases} }[/math] 称关于 [math]\displaystyle{ a,p }[/math] 的二元运算 [math]\displaystyle{ \left(\frac{a}{p}\right) }[/math] 为勒让德符号(Legendre symbol)， 也称关于 [math]\displaystyle{ a }[/math] 的一元运算 [math]\displaystyle{ \left(\frac{a}{p}\right) }[/math] 为模 [math]\displaystyle{ p }[/math] 的勒让德符号(Legendre symbol modulo [math]\displaystyle{ p }[/math])，
意义
[math]\displaystyle{ \left(\frac{a}{p}\right)=1 }[/math] 则二次同余方程 [math]\displaystyle{ x^2 \equiv a \pmod p }[/math] 有解。
性质
对 [math]\displaystyle{ a }[/math] ：
- 周期性，且周期整除 [math]\displaystyle{ p }[/math] 。即 [math]\displaystyle{ \left(\frac{a}{p}\right) = \left(\frac{a+p}{p}\right) }[/math] 。
- 或者说 [math]\displaystyle{ a\equiv b\pmod p \Rightarrow \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right) }[/math] 。
- 完全乘性，即：
- [math]\displaystyle{ \left(\frac{1}{p}\right) = 1 }[/math] 。
- [math]\displaystyle{ \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) }[/math] 。
- 二次剩余的定义，有 [math]\displaystyle{ \left(\frac{x^2}{p}\right) = \begin{cases} 1 &, p\not\mid x \\ 0 &, p\mid x \end{cases} }[/math] 。
相关定理：
- 欧拉准则，有 [math]\displaystyle{ \left(\frac{a}{p}\right) = a^{\frac{p-1}{2}} }[/math]
- 二次互反律，有 [math]\displaystyle{ \left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}} }[/math] 。
对 [math]\displaystyle{ a }[/math] 的特殊值：
- 根据欧拉准则，有
- [math]\displaystyle{ \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = \begin{cases} 1 &, p\equiv 1 \pmod 4 \\ -1 &, p \equiv 3 \pmod 4 \end{cases} }[/math] ；
- 根据高斯引理计数，有：
- [math]\displaystyle{ \left(\frac{2}{p}\right) = \begin{cases} 1 &, p\equiv \pm1 \pmod 8 \\ -1 &, p \equiv \pm3 \pmod 8 \end{cases} }[/math] ；
- 也可以表达为 [math]\displaystyle{ (-1)^{\frac{p^2-1}{8}} }[/math] ；
- 对 [math]\displaystyle{ p\neq 3 }[/math] ，由高斯引理讨论计数，或由高斯二次互反律，从 [math]\displaystyle{ \left(\frac{3}{p}\right)\left(\frac{p}{3}\right) = (-1)^{\frac{p-1}{2}} }[/math] 分别讨论 [math]\displaystyle{ (-1)^{\frac{p-1}{2}} }[/math] 和 [math]\displaystyle{ \left(\frac{p}{3}\right) }[/math] 可得：
- [math]\displaystyle{ \left(\frac{3}{p}\right) = \begin{cases} 1 &, p\equiv \pm1 \pmod 12 \\ -1 &, p \equiv \pm5 \pmod 12 \end{cases} }[/math] ；
- 也可以表达为 [math]\displaystyle{ (-1)^{\left\lfloor \frac{p+1}{6} \right\rfloor} }[/math] ；
- 对 [math]\displaystyle{ p\neq 5 }[/math] ，由高斯引理讨论计数，或由高斯二次互反律，从 [math]\displaystyle{ \left(\frac{5}{p}\right)\left(\frac{p}{5}\right) = (-1)^{\frac{p-1}{2}} }[/math] 分别讨论 [math]\displaystyle{ (-1)^{\frac{p-1}{2}} }[/math] 和 [math]\displaystyle{ \left(\frac{p}{5}\right) }[/math] 可得：
- [math]\displaystyle{ \left(\frac{5}{p}\right) = \begin{cases} 1 &, p\equiv \pm1 \pmod 5 \\ -1 &, p \equiv \pm2 \pmod 5 \end{cases} }[/math] ；
- 也可以表达为 [math]\displaystyle{ (-1)^{\left\lfloor \frac{2p+2}{5} \right\rfloor} }[/math] 。