勒让德符号,或二次特征,是一个由阿德里安-马里·勒让德在1798年尝试证明二次互反律时引入的函数[1][2]。这个符号是许多高次剩余符号的原型[3];其它延伸和推广包括雅可比符号、克罗内克符号、希尔伯特符号,以及阿廷符号。
勒让德符号
(有时为了印刷上的方便,写成(a|p))有下列定义:
| | 如果 |
如果 ,且对于某个整数 |
如果不存在整数 ,使得 。 |
如果(a|p) = 1,a 便称为二次剩余(mod p);如果(a|p) = −1,则 a 称为二次非剩余(mod p)。通常把零视为一种特殊的情况。
a 等于0、1、2、……时的周期数列(a|p),又称为勒让德数列,有时把{0,1,-1}的数值用{1,0,1}或{0,1,0}代替。[4]
勒让德原先把他的符号定义为:[5]
![{\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}},\left({\frac {a}{p}}\right)\in \{-1,1\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e9ae7bf9e03010a40ce08acdde48fd7194649b5)
欧拉在之前证明了如果a是二次剩余(mod p),(a|p) = 1;如果a是二次非剩余,(a|p) = -1;这个结论现在称为欧拉准则。
除了这个基本定义式以外,还有其它(a|p)的表达式,它们当中有许多都在二次互反律的证明中有所使用。
高斯证明了[6]如果
,那么:
![{\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}]}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/783ff164dffe529838a5998a905661e7ef518973)
这是他对二次互反律的第四个[7]、第六个[8],以及许多[9]后续的证明的基础。参见高斯和。
克罗内克的证明[10]是建立了
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb855773ec77763bc68495473b6fefff26e22d18)
然后把p和q互换。
艾森斯坦的一个证明[11]是从以下等式开始:
![{\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)}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/114dc4c88125893e642b55a65e8aa89b6cc1396e)
把正弦函数用椭圆函数来代替,他也证明了三次和四次互反律。
斐波那契数1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ……由递推公式F1 = F2 = 1,Fn+1 = Fn + Fn-1定义。
如果p是素数,则:
![{\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}},\;\;\;F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e181d4768c27c0211aa72c190c3de029ad791a7e)
例如:
![{\displaystyle ({\tfrac {2}{5}})=-1,\,\,F_{3}=2,F_{2}=1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bff73e7a5b7e297cc026f6eb820aea916e66df5c)
![{\displaystyle ({\tfrac {3}{5}})=-1,\,\,F_{4}=3,F_{3}=2,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ddb09711de46633a3aed5eb8c7645fd82c6d018e)
![{\displaystyle ({\tfrac {5}{5}})=\;\;\,0,\,\,F_{5}=5,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9590479e8a36276e7200a270774c51af114127cc)
![{\displaystyle ({\tfrac {7}{5}})=-1,\,\,F_{8}=21,\;\;F_{7}=13,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/690f49d30be9715186b6b16bbfd955dd19143466)
![{\displaystyle ({\tfrac {11}{5}})=+1,F_{10}=55,F_{11}=89.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/667113c068487285ac767f49eef07de6a4f19a2e)
这个结果来自卢卡斯数列的理论,在素性测试中有所应用。[12]参见沃尔-孙-孙素数。
勒让德符号有许多有用的性质,可以用来加速计算。它们包括:
(它是一个完全积性函数。这个性质可以理解为:两个剩余或非剩余的乘积是剩余,一个剩余与一个非剩余的乘积是非剩余。)
- 如果a ≡ b (mod p),则
![{\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22c53d660aed6373e99b8e0feb7d9801186b2d41)
![{\displaystyle \left({\frac {a^{2}}{p}}\right)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5b6f43df4f40202dbf365146ae39d7037387df5)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd3bcfb31b3ac3ef72a6838ba0d0c58a2f236f74)
这个性质称为二次互反律的第一补充。
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d90e3a78bfe75d1c4f4bfdd49690bd3af4673562)
这个性质称为二次互反律的第二补充。一般的二次互反律为:
- 如果p和q是奇素数,则
![{\displaystyle \left({\frac {q}{p}}\right)=\left({\frac {p}{q}}\right)(-1)^{{\frac {p-1}{2}}{\frac {q-1}{2}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/966e6a0e5a66971e0c4d850b4a1627a598863d46)
参见二次互反律和二次互反律的证明。
以下是一些较小的p的值的公式:
- 对于奇素数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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d1c563452f82cfaf77baaecb82ed16888381a6b)
- 对于奇素数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}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e1ed5877d9a39798e4afdb699e61d13b8071e59)
但一般直接把剩余和非剩余列出更简便:
- 对于奇素数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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a70b4a7cc4d99b0842fa9b6bc71209398f6f8eeb)
勒让德符号(a|p)是一个狄利克雷特征(mod p)。
以上的性质,包括二次互反律,可以用来计算任何勒让德符号。例如:
![{\displaystyle \left({\frac {12345}{331}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/827ce8eb12cd064d538fba78851cdcf32f5237e9)
![{\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {823}{331}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/239c0bd33998501f6f040a0a53f0757f665b1cb8)
![{\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {161}{331}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e27dfd260354631933b8f1a96998af6093847c45)
![{\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {7}{331}}\right)\left({\frac {23}{331}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/827eecd5ac37c8bb9f0e1708f0752d2741785690)
![{\displaystyle =(-1)\left({\frac {331}{3}}\right)\left({\frac {331}{5}}\right)(-1)\left({\frac {331}{7}}\right)(-1)\left({\frac {331}{23}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e15893c92c8e69189b6dbe3fc84878f80016cf56)
![{\displaystyle =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {9}{23}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9f3d05e8faa1196ae844ff490e380543cf4cd9d)
![{\displaystyle =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {3}{23}}\right)^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ab36b474cf5d1e547a7c818815d1588f528dcff)
![{\displaystyle =-\left(1\right)\left(1\right)\left(1\right)\left(1\right)=-1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cf73f630b227bdea61d980f4d945bb8fc2dfafc)
- 雅可比符号是勒让德符号的一个推广,允许底数为合数,但底数仍然必须是奇数和正数。这个推广提供了计算所有勒让德符号的一个有效的方法。
- 一个进一步的推广是克罗内克符号,把底数的范围延伸到一切整数。
- ^ A. M. Legendre Essai sur la theorie des nombres Paris 1798, p 186
- ^ 在欧拉(1783年)和勒让德(1786年)的作品中有所讲述。首先由高斯在1796年证明,在DA(1801年)出版;arts. 107-144(第一个证明),253-262(第二个证明)
- ^ Lemmermeyer, p.xiv “即使在像双二次互反律的简单情况下,我们仍然需要区分四个不同的符号,即Z[i]中的二次和双二次剩余符号,Z中的勒让德符号,以及Z中的有理二次剩余符号……”
- ^ Jeong-Heon Kim and Hong-Yeop Song, "Trace Representation of Legendre Sequences," Designs, Codes, and Cryptography 24, p. 343–348 (2001).
- ^ Lemmermeyer p. 8
- ^ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463-495. Crandall & Pomerance p. 92
- ^ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463-495
- ^ Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadritischen Resten" (1818) reprinted in Untersuchungen ... pp. 501-505
- ^ 在Lemmermeyer的最初四章有所讲述
- ^ Lemmermeyer, ex. p. 31, 1.34
- ^ Lemmermeyer, pp. 236 ff.
- ^ 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