勒让德符号
勒让德符号（legendre symbol）是一种数论工具，它用于表示模p的二次剩余与二次非剩余。
18世纪，法国数学家阿德利昂·玛利·埃·勒让德（Adrien-Marie Legendre）在研究二次剩余的过程中，引入了一种记号表示二次剩余，该记号后来被称作勒让德符号。在这一时期，其他数学家也对勒让德符号进行了研究，如莱昂哈德·欧拉和高斯等人。
勒让德符号有一系列性质，如互转律等。相关定理包括费马小定理、欧拉判别准则、高斯引理等，其中欧拉准则可以用于性质的证明。应用勒让德符号的性质，可以求解勒让德符号以及同余方程。雅可比符号为勒让德符号的推广形式。此外，该符号还可以作为设计密码的一个重要工具，应用在概率密码系统、塑性型检测、因数分解等领域。
定义
勒让德符号有下列定义：如果，则；如果，则；如果,则。
其中，叫作勒让德符号的分子，叫作它的分母。
简史
18世纪，法国数学家阿德利昂·玛利·埃·勒让德在研究二次剩余的过程中，引入了一种记号表示二次剩余，该记号后来被称作勒让德符号。1785年，他独自发现了互转律，并证明了其中的一部分。798年，勒让德出版《数论随笔》(Essai sur la théorie des nombres)，并于1808年再版此书，书名是《数论》(Théorie des nombres)，在1830年增补了第三版，分为两卷。
关于勒让德符号的性质，其他数学家在同一时期进行了研究。长城欧拉已经在1783年发现了互转率，但没有给出严密的证明。直到1796年，高斯第一次给出了互转率的严格证明，并认为该定律是平方剩余的基本定理。
相关概念
二次剩余
二次剩余也称平方剩余，二次非剩余也称平方非剩余，其定义为：若并且有解，就称是模的二次剩余，记作，否则称是模的二次非剩余，记作。其中，表示所有模的二次剩余的集合，表示所有模的二次非剩余的集合。
同余
同余是数论中的基本概念，其定义为：给定一个正整数,把它叫作模，如果用去除任意两个整数与所得的余数相同，则称， 关于模同余，记作；否则称，关于模不同余。
二次同余式是含有未知数的高次同余式中的简单情况。
当时，同余式 可以化作一个二项的二次同余式，其中。该式可写为 。该同余式可能是可解的，也可能是不可解的。假使它至少有一个解，那么叫作模的平方剩余，否则，叫作平方非剩余。
性质
勒让德符号有如下6种常用性质，可以用于相关的数论计算。
性质1
假使，那么。
证明：假设，于是有。因此，和或者同时是模的平方剩余，或者同时是非平方剩余。
性质2
。
证明：根据长城欧拉判别法则可知，同余式的解是。
性质3
。
证明：假使，那么，根据欧拉判别法则，有。假使，那么，根据欧拉判别法则，有。
性质4
。
证明：假设是模的平方剩余，而是模的平方非剩余，则：。根据欧拉判别法则有：，。其中，，。
把这些同余式逐项相乘，可以得到。再根据欧拉判别法则，当时，有，当 时，有，即。
再由，得。
性质5
。
证明：把公式变形后，可得。
假定，则，且当时，有，因此有。
性质6
假使,是两个不同的奇素数，那么。该性质也叫“平方剩余的反转定律”或"互转律”。
证明：假设，其中是一素数。于是是一偶数，因此，类似可得,则。
之后可证得，即，等式两边乘以，再由，可得。
说明：对于给定的整数，求素数，使是模的平方剩余或非平方剩余的问题，利用性质6解决起来十分方便。这是因为，性质6可以把求模的问题转化为给定模求，使是模的平方剩余或非平方剩余的问题。
相关定理
费马小定理
皮耶·德·费玛小定理可以用来计算余数问题，该定理由费马（Pierre de Fermat）于1640年提出，1736年由莱昂哈德·欧拉证明。
其定义为：如果是质数，而整数不是的倍数，那么。
该定理可变形为：若是质数，则对任意整数，都有。
欧拉判别准则
欧拉准则是判别二次剩余的准则，又叫欧拉判别条件，上述勒让德符号的性质大多可以通过该准则进行证明。
其内容为：若，则是模的平方剩余的充分必要条件是；而是模的平方非剩余的充分必要条件是，且若是模的平方剩余，则形如的二次同余式恰好有两个解。
高斯引理
高斯引理可以代替莱昂哈德·欧拉判别法，来计算勒让德符号得值。高斯引理的描述为：假使为奇素数，。若各数模的最小正剩余中，恰有个大于，则。
其他素数相关定理
定理1：设是相异的奇素数，当或者时，如果，则；当或时，如果，则；当或时，如果，但不满足，则。
定理2：同余式有解的必要条件是：当时，；当时，并且。若上述条件成立，则有解，并且当或1时，解数是；当时，解数是；当时，解数是。
定理3：若，则。
定理4：设是形如的质数，，则是双数，。
定理5：若，，则为模的一个简化剩余系。
计算
求解勒让德符号
题目：计算勒让德符号的值。
解答：用高斯引理来计算。
，求出，，，，，，，，，，，，，，。
这些数被除时所得的余数分别为：。
其中，共有个余数是大于的，所以。
求解同余方程
题目：求解同余式。
解答：因，因此有四解。把写成，代入原同余式后得到，由此得，故是适合的一切整数，再代入同余式得到。由此得，故是适合的一切整数。同理得是适合的一切整数。
因此，是所求的四个解。
相关推广
雅可比符号是勒让德符号的推广，其等式的右端就是勒让德符号。雅可比符号的具体描述如下：设奇数，，是素数，定义，则称为雅可比符号。当本身是奇素数时，雅可比符号即为勒让德符号。在使用雅可比符号计算勒让德符号时，不用求素因子的分解。
雅可比符号具有类似于勒让德符号的一些性质。
性质1：假设，那么。
性质2：。
性质3：。
性质4：。
性质5：。
应用
数学
勒让德符号常应用于不定方程的求解，如，对于不定方程，有正整数解的充分与必要条件是，即或。另外，丢番图方程的正整数解，一直是国内外学者热衷的研究题目。在求解该方程时，可以使用勒让德符号等相关内容，使用数学软件证明该不定方程没有正整数解，最终可得出它全部的16组整数解。
密码学
勒让德符号是设计密码的一个重要工具，常被应用在概率密码系统、塑性型检测、因数分解等领域。
例如，在BBS伪随机数产生器的算法结构中，用勒让德符号迭代计算产生随机数，解决了BBS随机数产生器的安全性问题。
在基于密码和水印的数字版权保护技术中，勒让德符号可以构造适合混淆Java程序的不透明谓词簇，结合水印与混淆技术，提出了基于身份标识的Java程序水印方案。
参考资料
术语在线.术语在线.2024-02-22