我们知道，把勒让德符号 (a|p) 中的 a 分解质因数（并可能提出个负号），利用 (uv|p)=(u|p)(v|p) ，我们只需求出形如 (q|p) 的值就行了，其中 q=-1,2 或奇素数。前两种情况已经讨论过，只剩下奇素数了。

    这也是二次互反律的最重要的一部分：对于不等的奇素数 p,q ，有

    证明它的一个容易理解的方法类似于上次求 (2|p) 的思路。为了表示出 (q|p) ，只需求 q^[(p-1)/2]。我们可以像上次一样，考虑这个式子：

    左边恰好有一项可以模 p 同余变成 1 或 -1 ，恰好有一项可以变成 2 或 -2 ，这样我们只需统计拿出了多少个负号。不过，为了叙述简单，我们换一种取法，把 1,2,3,...,(p-1)/2 换成 2,4,6,...,p-1 ：

    为什么这样写会简单，后面再说。先解释一下左边为什么可以通过模 p 同余，以及拿出若干负号变成右边。注意到左边没有 p 的倍数，没有两个数模 p 同余，并且没有两个数的和是 p 的倍数（若左边有两个数 2uq,2vq 的和是 p 的倍数，则 u+v 是 p 的倍数，但 u,v 均为不超过 (p-1)/2 的正整数，矛盾）。

    我们先通过模 p 同余，使左边的每个乘数都变成 1,2,3,...,p-1 以内的数。然后，再将每个奇数减去 p 变成偶数。显然此时没有 0 （否则它是 p 的倍数），没有两个数是相等的（否则它们一定模 p 同余），没有两个数互为相反数（否则它们的和是 p 的倍数）。所以它们的绝对值恰好是 2,4,6,...,p-1 的一个排列。

    左边拿出了多少负号？注意我们是把左边的每个数先变成它除以 p 的余数（最小正剩余），然后如果是奇数就再减去 p 拿出一个负号。我们可以用 -1 的某个数除以 p 的余数次方表示这个数有没有贡献出负号。

    也就是说我们可以写出下面的式子：

    其中 r_1,r_2,r_3,...,r_(p-1)/2 是 2q,4q,6q,...,(p-1)q 除以 p 的余数。也就是说

    这解释了当初为什么要取所有偶数，因为这样可以用 -1 的次方方便地写出整个式子。

    上面关于 r_k 的表达式可以简化，因为我们只关心它的奇偶性。首先 2kq 是个偶数可以扔掉，其次后面的减号可以变成加号，由于 p 是个奇数，整数乘以奇数不会改变它的奇偶性，因此乘数 p 可以扔掉。也就是说

    由此进一步简化上面的式子：

    现在只需求出最右边指数上的那个和式就行了，不过好像不是那么好求...这个和式看着不顺眼，我们可以利用公式

    来稍微变换一下（其中 a 是整数且 x 不是整数）。在这里我们令 x=2kq/p,a=q ，满足公式使用条件，而且由于 a-1 是偶数，我们只关心奇偶性，于是可以直接得到

    当然，我们不是把待变换和式的每一项都换掉。我们只换掉超过 [(p-1)/2]*q/p 的。容易说明替换之后和式恰好变成

    也就是说

    现在差最后一步，把右边指数上的和式搞出来。这个证明是以一个漂亮的图形说明来结尾的：

    带颜色的点都是整点，被直线 y=qx/p 分成两部分，并且没有点在直线上（因为 p,q 互质），观察绿点，横坐标为 k 的绿点，纵坐标可以取小于 qk/p 的正整数，于是有 [qk/p] 个不同的取值。绿点总数恰好是

    同理蓝点个数就是把此式的 p,q 交换，而绿点和蓝点总数显然为 (p-1)(q-1)/4 ，于是刚才那个和式就是 (p-1)(q-1)/4 。

    这样二次互反律就证完了。

    二次互反律的一个重要应用就是计算勒让德符号（也就是说判断 a 是否是奇素数 p 的二次剩余）。对于勒让德符号 (a|p) ，我们先把 a 分解质因数（并且可能提出一个负号），然后把 (a|p) 表示成 (-1|p),(2|p),(q|p) （ q 为奇素数）的乘积，前两个可以直接算出来，而 (q|p) 可以利用二次互反律翻转使“分母”变小。

    “分母”都知道啥意思吧...就是 (a|p) 里面的那个 p ...这是为了方便叙述...

    先看个例子：

    计算过程类似辗转相除法，计算的步数是很少的。不过，这个算法需要分解素因数，而对大数分解质因数还没有好的办法。我们可以试试能不能把勒让德符号直接翻转而不用管“分子”是不是奇素数。为此我们先把勒让德符号推广为“分母”为任意正奇数的情况（一般叫做雅可比符号）：定义

    其中 p_1,p_2,p_3,...,p_k 均为奇素数。这样“分母”就可以为任意正奇数了。不过要注意，雅可比符号 (a|b) 不表示 a 是不是模 b 的二次剩余。

    接下来我们推广二次互反律。首先考虑“分子”为 -1 的情况。此时有

    我们如果能证明

    就好了，这说明以前的二次互反律仍然成立。事实上，此式左边是 1 还是 -1 取决于各个 p_i 中被 4 除余 3 的数有偶数个还是奇数个。如果有偶数个，左边就是 1 ，否则就是 -1 。而各个 p_i 的乘积被 4 除余 1 还是余 3 也取决于各个 p_i 中被 4 除余 3 的数有偶数个还是奇数个。如果有偶数个，右边就是 1 ，否则就是 -1 。于是此式是成立的。

    接下来是“分子”为 2 的情况。仍然沿用类似的方法我们可以得到：

    我们只要证明

    就行了，这跟上面几乎完全一样（下面这段话我就是复制过来改的...）。事实上，此式左边是 1 还是 -1 取决于各个 p_i 中被 8 除余 ±3 的数有偶数个还是奇数个。如果有偶数个，左边就是 1 ，否则就是 -1 。而各个 p_i 的乘积被 8 除余 ±1 还是余 ±3 也取决于各个 p_i 中被 8 除余 ±3 的数有偶数个还是奇数个。如果有偶数个，右边就是 1 ，否则就是 -1 。于是此式是成立的。

    最后只剩下“分子”为正奇数的情况。我们只需证明

    先对左边下手。

    左边式子有点大，用了连乘号...左边各个乘数不是 1 就是 -1 ，我们只要数出来有多少个 -1 就行了。而左边含 p_u,q_v 的那一项是 -1 ，当且仅当 p_u,q_v 同时被 4 除余 3 。根据乘法原理，左边 -1 的个数，恰好就等于 p_u 中被 4 除余 3 的数的个数乘以 q_v 中被 4 除余 3 的数的个数。我们立即得到，左边等于 -1 ，当且仅当 p_u 中被 4 除余 3 的数有奇数个，同时 q_v 中被 4 除余 3 的数也有奇数个，也就等价于各个 p_u 的乘积以及各个 q_v 的乘积被 4 除均余 3 。

    而未化简的右边等于 -1 ，当且仅当右边的指数为奇数，也就是各个 p_u 的乘积以及各个 q_v 的乘积被 4 除均余 3 。这样这个结论就证完了。

    我们把三条放在一起写：

    其中 a,b 均为正奇数。这样我们就可以避开分解素因数，很快地求出勒让德符号的值。最后举个例子：

    后面，我们将讨论哪些素数可以表示为两个平方数之和。