# 勒让德符号

## 定义

 ${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\quad 0\\+1\\-1\end{cases}}}$ ${\displaystyle \quad }$ 如果${\displaystyle a\equiv 0{\pmod {p}}}$ 如果${\displaystyle a\not \equiv 0{\pmod {p}}}$，且对于某个整数${\displaystyle x,x^{2}\equiv \;a{\pmod {p}}}$ 如果不存在整数${\displaystyle x}$，使得${\displaystyle x^{2}\equiv \;a{\pmod {p}}}$。

a 等于0、1、2、……时的周期数列(a|p)，又称为勒让德数列，有时把{0,1,-1}的数值用{1,0,1}或{0,1,0}代替。[4]

## 勒让德符号的公式

${\displaystyle \left({\frac {a}{p}}\right)=\pm 1\equiv a^{\frac {p-1}{2}}{\pmod {p}}.}$

${\displaystyle \left({\frac {a}{p}}\right)={\frac {1+\zeta ^{a}+\zeta ^{4a}+\zeta ^{9a}+\dots +\zeta ^{(p-1)^{2}a}}{1+\zeta +\zeta ^{4}+\zeta ^{9}+\dots +\zeta ^{(p-1)^{2}}}}={\frac {2(1+\zeta ^{a}+\zeta ^{4a}+\zeta ^{9a}+\dots +\zeta ^{(p-1)^{2}a})}{{\sqrt {p}}(1+i)[1+(-i)^{p}]}}.}$

${\displaystyle \left({\frac {p}{q}}\right)=\operatorname {sgn} \prod _{i=1}^{\frac {q-1}{2}}\prod _{k=1}^{\frac {p-1}{2}}\left({\frac {k}{p}}-{\frac {i}{q}}\right)}$

${\displaystyle \left({\frac {q}{p}}\right)=\prod _{n=1}^{\frac {p-1}{2}}{\frac {\sin({\frac {2\pi }{p}}qn)}{\sin({\frac {2\pi }{p}}n)}}.}$

### 其它含有勒让德符号的公式

${\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}},\;\;\;F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}.}$

${\displaystyle ({\tfrac {2}{5}})=-1,\,\,F_{3}=2,F_{2}=1,}$
${\displaystyle ({\tfrac {3}{5}})=-1,\,\,F_{4}=3,F_{3}=2,}$
${\displaystyle ({\tfrac {5}{5}})=\;\;\,0,\,\,F_{5}=5,}$
${\displaystyle ({\tfrac {7}{5}})=-1,\,\,F_{8}=21,\;\;F_{7}=13,}$
${\displaystyle ({\tfrac {11}{5}})=+1,F_{10}=55,F_{11}=89.}$

## 性质

• ${\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)}$（它是一个完全积性函数。这个性质可以理解为：两个剩余或非剩余的乘积是剩余，一个剩余与一个非剩余的乘积是非剩余。）
• 如果ab (mod p)，则${\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}$
• ${\displaystyle \left({\frac {a^{2}}{p}}\right)=1}$
• ${\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}+1{\mbox{ if }}p\equiv 1{\pmod {4}}\\-1{\mbox{ if }}p\equiv 3{\pmod {4}}\end{cases}}}$

• ${\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}={\begin{cases}+1{\mbox{ if }}p\equiv 1{\mbox{ or }}7{\pmod {8}}\\-1{\mbox{ if }}p\equiv 3{\mbox{ or }}5{\pmod {8}}\end{cases}}}$

• 如果pq是奇素数，则${\displaystyle \left({\frac {q}{p}}\right)=\left({\frac {p}{q}}\right)(-1)^{{\frac {p-1}{2}}{\frac {q-1}{2}}}.}$

• 对于奇素数p${\displaystyle \left({\frac {3}{p}}\right)=(-1)^{\left\lceil {\frac {p+1}{6}}\right\rceil }={\begin{cases}+1{\mbox{ if }}p\equiv 1{\mbox{ or }}11{\pmod {12}}\\-1{\mbox{ if }}p\equiv 5{\mbox{ or }}7{\pmod {12}}\end{cases}}}$
• 对于奇素数p${\displaystyle \left({\frac {5}{p}}\right)=(-1)^{\left\lfloor {\frac {p-2}{5}}\right\rfloor }={\begin{cases}+1{\mbox{ if }}p\equiv 1{\mbox{ or }}4{\pmod {5}}\\-1{\mbox{ if }}p\equiv 2{\mbox{ or }}3{\pmod {5}}\end{cases}},}$

• 对于奇素数p${\displaystyle \left({\frac {7}{p}}\right)={\begin{cases}+1{\mbox{ if }}p\equiv 1,3,9,19,25,{\mbox{ or }}27{\pmod {28}}\\-1{\mbox{ if }}p\equiv 5,11,13,15,17,{\mbox{ or }}23{\pmod {28}}\end{cases}}}$

## 计算例子

${\displaystyle \left({\frac {12345}{331}}\right)}$
${\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {823}{331}}\right)}$
${\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {161}{331}}\right)}$
${\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {7}{331}}\right)\left({\frac {23}{331}}\right)}$
${\displaystyle =(-1)\left({\frac {331}{3}}\right)\left({\frac {331}{5}}\right)(-1)\left({\frac {331}{7}}\right)(-1)\left({\frac {331}{23}}\right)}$
${\displaystyle =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {9}{23}}\right)}$
${\displaystyle =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {3}{23}}\right)^{2}}$
${\displaystyle =-\left(1\right)\left(1\right)\left(1\right)\left(1\right)=-1.}$

## 相关函数

• 雅可比符号是勒让德符号的一个推广，允许底数为合数，但底数仍然必须是奇数和正数。这个推广提供了计算所有勒让德符号的一个有效的方法。
• 一个进一步的推广是克罗内克符号，把底数的范围延伸到一切整数。

## 注释

1. ^ A. M. Legendre Essai sur la theorie des nombres Paris 1798, p 186
2. ^ 在欧拉（1783年）和勒让德（1786年）的作品中有所讲述。首先由高斯在1796年证明，在DA（1801年）出版；arts. 107-144（第一个证明），253-262（第二个证明）
3. ^ Lemmermeyer, p.xiv “即使在像双二次互反律的简单情况下，我们仍然需要区分四个不同的符号，即Z[i]中的二次和双二次剩余符号，Z中的勒让德符号，以及Z中的有理二次剩余符号……”
4. ^ Jeong-Heon Kim and Hong-Yeop Song, "Trace Representation of Legendre Sequences," Designs, Codes, and Cryptography 24, p. 343–348 (2001).
5. ^ Lemmermeyer p. 8
6. ^ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463-495. Crandall & Pomerance p. 92
7. ^ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463-495
8. ^ Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadritischen Resten" (1818) reprinted in Untersuchungen ... pp. 501-505
9. ^ 在Lemmermeyer的最初四章有所讲述
10. ^ Lemmermeyer, ex. p. 31, 1.34
11. ^ Lemmermeyer, pp. 236 ff.
12. ^ Ribenboim, p. 64; Lemmermeyer, ex 2.25-2.28, pp. 73-74.

## 参考文献

• Gauss, Carl Friedrich; Maser, H.（德文翻译者）, Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory)（第二版）, New York: Chelsea, 1965, ISBN 0-8284-0191-8
• Gauss, Carl Friedrich; Clarke, Arthur A.（英文翻译者）, Disquisitiones Arithmeticae（第二，修订版）, New York: Springer, 1986, ISBN 0387962549
• Ireland, Kenneth; Rosen, Michael, A Classical Introduction to Modern Number Theory（第二版）, New York: Springer, 1990, ISBN 0-387-97329-X