先放资料。
前置技能点：#
剩余系**:设模为m,则根据余数可将所有的整数分成m类，分别记成[0],[1],[2],…[m-1]****，**
这m个数**{0,1,2,****…****m-1}**称为一个完全剩余系，
每个数称为相应类的代表元。
当m=10（偶数）时候，则{0,1,2,3,4,5,6,7,8,9}是最小非负完全剩余系
{-5,-4,-3,-2,-1,0,1,2,3,4,5} 是绝对值最小完全剩余系
{-4,-3,-2,-1,0,1,2,3,4,5} 绝对值最小
{1,2,3,4,5,6,7,8,9,10}是最小正完全剩余系
简化剩余系：在每个剩余类选取至1个与m互素代表元构成简化剩余系。
当m=10则，{0,1,2,3,4,5,6,7,8,9} 完全剩余系
{1,3,7,9}是简化剩余系(x,10)=1
当m=5则，{0,1,2,3,4}为完全剩余系，
{1,2,3,4}是简化剩余系，因为除去余0(正好是倍数)外，其它都互素。
f(m)=欧拉函数=|{t|0<t<m, (t, m)=1}|
=简化剩余系的元素个数
设_p_为奇质数，a_是一个与_p互质的整数。考虑以下数组：\( a,2a,3a,\dots ,{\frac {p-1}{2}}a \) 以及它们对_p_的最小非负剩余。这些剩余两两不等（kk:这些剩余两两不等的证明：可以考虑反证，假设两个不同的数x,y对于p同余， 那么x-y和0关于p同余，而x-y同时关于a同余，a与p互质，矛盾。因此这些剩余两两不等），因此我们共有\( \frac{p-1}{2} \) 个两两不等的介于1和_p（kk：这里似乎有问题，如果剩余是在1..p之间，那么前面应该是说最小正剩余而不是最小非负剩余，最小非负剩余应该是在0..p-1之间）之间的整数：\( t_{1},t_{2},t_{3},\dots ,t_{\frac {p-1}{2}} \) 。设其中有_n_个数比_p/2大，那么高斯引理声称：\( \left({\frac {a}{p}}\right)=(-1)^{n} \)
上式左边是勒让德符号，当其值为+1时，表示_a_是模_p_的二次剩余；其值为-1时，表示_a_是模_p_的二次非剩余。
用通俗的语言来说，就是：\( t_{1},t_{2},t_{3},\dots ,t_{\frac {p-1}{2}} \) 里面比_p_/2大的有偶数个，那么_a_是模_p_的二次剩余，如果有奇数个，那么_a_是模_p_的二次非剩余。
正片：#
定义：
勒让德符号\( ({\tfrac {a}{p}}) \) （有时为了印刷上的方便，写成(a|p))有下列定义：
\( \left({\frac {a}{p}}\right)={\begin{cases}\quad 0\\+1\\-1\end{cases}} \) 如果\( a\equiv 0{\pmod {p}} \) 如果\( a\not \equiv 0{\pmod {p}} \) ，且对于某个整数\( x,x^{2}\equiv \;a{\pmod {p}} \)
如果不存在整数\( x \) ，使得\( x^{2}\equiv \;a{\pmod {p}} \) 。
如果(a|p) = 1，a 便称为二次剩余(mod p)；如果(a|p) = −1，则 a 称为二次非剩余(mod p)。通常把零视为一种特殊的情况。
性质：
勒让德符号有许多有用的性质，可以用来加速计算。它们包括：
- \( \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right) \)
（它是一个**完全积性函数**(kk:g(a)g(b)=g(ab)对于任意正整数a,b都成立，不需要gcd(a,b)=1，完全积性真是爽哭了…)。这个性质可以进一步理解为：两个剩余或非剩余的乘积是剩余，一个剩余与一个非剩余的乘积是非剩余。（kk:因为负负得正，正正得正…））
如果_a_ ≡ b (mod p)，则\( \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right) \)
\( \left({\frac {a^{2}}{p}}\right)=1 \)
\( \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}+1{\text{ if }}p\equiv 1{\pmod {4}}\\-1{\text{ if }}p\equiv 3{\pmod {4}}\end{cases}} \)
这个性质称为二次互反律的第一补充。
- \( \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}={\begin{cases}+1{\text{ if }}p\equiv 1{\text{ or }}7{\pmod {8}}\\-1{\text{ if }}p\equiv 3{\text{ or }}5{\pmod {8}}\end{cases}} \)
这个性质称为二次互反律的第二补充。一般的二次互反律为：
- 如果_p_和_q_是奇素数，则\( \left({\frac {q}{p}}\right)=\left({\frac {p}{q}}\right)(-1)^{{{\frac {p-1}{2}}{\frac {q-1}{2}}}}. \)
以下是一些较小的_p_的值的公式：
对于奇素数_p_，\( \left({\frac {3}{p}}\right)=(-1)^{\left\lceil {\frac {p+1}{6}}\right\rceil }={\begin{cases}+1{\text{ if }}p\equiv 1{\text{ or }}11{\pmod {12}}\\-1{\text{ if }}p\equiv 5{\text{ or }}7{\pmod {12}}\end{cases}} \)
对于奇素数_p_，\( \left({\frac {5}{p}}\right)=(-1)^{\left\lfloor {\frac {p-2}{5}}\right\rfloor }={\begin{cases}+1{\text{ if }}p\equiv 1{\text{ or }}4{\pmod 5}\\-1{\text{ if }}p\equiv 2{\text{ or }}3{\pmod 5}\end{cases}}, \)
但一般直接把剩余和非剩余列出更简便：
- 对于奇素数_p_，\( \left({\frac {7}{p}}\right)={\begin{cases}+1{\text{ if }}p\equiv 1,3,9,19,25,{\text{ or }}27{\pmod {28}}\\-1{\text{ if }}p\equiv 5,11,13,15,17,{\text{ or }}23{\pmod {28}}\end{cases}} \)
勒让德符号(a|p)是一个狄利克雷特征(mod p)。
计算勒让德符号的一个例子：
\[ \left({\frac {12345}{331}}\right) \]\[ =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {823}{331}}\right) \]（完全积性）
\[ =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {161}{331}}\right) \]（161和823关于331同余）
\[ =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {7}{331}}\right)\left({\frac {23}{331}}\right) \]（完全积性）
\[ =(-1)\left({\frac {331}{3}}\right)\left({\frac {331}{5}}\right)(-1)\left({\frac {331}{7}}\right)(-1)\left({\frac {331}{23}}\right) \]（二次互反律）
\[ =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {9}{23}}\right) \]（同余数）
\[ =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {3}{23}}\right)^{2} \]（完全积性，平方的形式值一定为1）
\[ =-\left(1\right)\left(1\right)\left(1\right)\left(1\right)=-1. \]（分别计算，可以参考小素数时的分段函数，具体的计算方法见下文）
维基百科_欧拉准则（用来计算勒让德符号）
若\( p \) 是奇质数且\( p \) 不能整除\( d \) ，则：
\( d \)是模\( p \) 的二次剩余当且仅当：\( d^{\frac {p-1}{2}}\equiv 1{\pmod {p}} \)
\( d \)是模\( p \) 的非二次剩余当且仅当：\( d^{\frac {p-1}{2}}\equiv -1{\pmod {p}} \)
**以勒让德符号表示，即为： \( d^{\frac {p-1}{2}}\equiv \left({\frac {d}{p}}\right){\pmod {p}} \) **
例子一：对于给定数，寻找其为二次剩余的模数#
令_a_ = 17。对于怎样的质数_p_，17是模_p_的二次剩余呢？
根据判别法里给出的准则，我们可以从小的质数开始检验。
首先测试_p_ = 3。我们有：17(3 − 1)/2 = 171 ≡ 2 (mod 3) ≡ -1 (mod 3)，因此17不是模3的二次剩余。
再来测试_p_ = 13。我们有：17(13 − 1)/2 = 176 ≡ 1 (mod 13)，因此17是模13的二次剩余。实际上我们有：17 ≡ 4 (mod 13)，而22 = 4.
运用同余性质和勒让德符号可以加快检验速度。继续算下去，可以得到：
对于质数_p_ =\( 13,19,\cdots \)，(17/p) = +1（也就是说17是模这些质数的二次剩余）。
对于质数_p_ =\( 3,5,7,11,23,\cdots \)，(17/p) = -1（也就是说17是模这些质数的二次非剩余）。
（**kk：简单地说，就是从小到大枚举质数p，验证a^((p-1)/2)）%p等于1还是-1.）**#
例子二：对指定的质数_p_，寻找其二次剩余#
哪些数是模17的二次剩余？
我们可以手工计算：（kk：手算考虑数的平方是因为，勒让德符号是完全积性函数&&\( \left({\frac {a^{2}}{p}}\right)=1 \) ）
12 = 1 22 = 4 32 = 9 42 = 16 52 = 25 ≡ 8 (mod 17) 62 = 36 ≡ 2 (mod 17) 72 = 49 ≡ 15 (mod 17) 82 = 64 ≡ 13 (mod 17)于是得到：所有模17的二次剩余的集合是\( {1,2,4,8,9,13,15,16} \) 。要注意的是我们只需要算到8，因为9=17-8，9的平方与8的平方模17是同余的：92 = (−8)2 = 82 ≡ 13 (mod 17).（同理不需计算比9大的数）。
但是对于验证一个数是不是模17的二次剩余，就不必将所有模17的二次剩余全部算出。比如说要检验数字3是否是模17的二次剩余，只需要计算3(17 − 1)/2 = 38 ≡ 812 ≡ ( − 4)2 ≡ − 1 (mod 17)，然后由欧拉准则判定3不是模17的二次剩余。
对于两个奇素数\( p \) 和 \( q \) ，\( \left({\frac {p}{q}}\right)\cdot \left({\frac {q}{p}}\right)=(-1)^{{{\frac {(p-1)(q-1)}{4}}}} \)
其中\( \left({\tfrac {p}{q}}\right) \) 是勒让德符号。
关于二次互反律的证明就不多说了。据说高斯一次给出了五个（还是七个？)，到现在一共有200+种证明。
然后感觉二次互反律真是太神了，太美了，真的被震撼到了 orz