二次剩余是个非常好玩的东西...为了讨论而次同余方程，我们将引入二次剩余来研究下面这类最简单的二次同余方程：

http://s4/mw690/0032UzSRzy6HROMMIAr83&690
    其中 a 为整数， p 为奇素数， x 为未知整数。当然，我们不妨限定 a,x 均在 0,1,2,3,...,p-1 内。不过，为了叙述方便我们又经常把 0 去掉（当 a=0 时显然有唯一解 x=0 ）。第一个问题是：

    对于哪些 a 方程有解？如果有的话有几个解？

    第一个问题暂时不好回答，不过我们可以证明，使方程有解的 a 的取值恰好是 (p-1)/2 个，恰好是全部取值个数的一半。若方程有解，则恰好有两个解，且这两个解的和为 p 。

    为了证明它，我们考虑 1,2,3,...,p-1 这些数的平方。我们关心的是这些平方有没有重复（模 p 同余）的。假设这里面有两个不相同的平方 u^2,v^2 模 p 同余，则有：

http://s2/mw690/0032UzSRzy6HRPXpilXe1&690

    素数 p 整除两个整数之积，则必整除其中一个。由于 u-v 不可能是 p 的倍数（否则有 u=v ），则有 u+v 是 p 的倍数，也就是说 u+v=p 。

    这样，我们就知道了： 1,2,3,...,p-1 这些数的平方必然可以两两配对，每对都模 p 同余，除此之外不在同一对的两个数模 p 不同余。这样，实质不同的平方数只有 (p-1)/2 个，它们对应着使方程有解的 a 的 (p-1)/2 个取值，而且每个使方程有解的 a 的取值都对应着两个平方数。这就证完了。

    我们把这 (p-1)/2 个取值称作模 p 的二次剩余，另外 (p-1)/2 个使方程无解的 a 称作模 p 的二次非剩余。另外规定如果 a 是模 p 的二次剩余/二次非剩余，那么与 a 模 p 同余的数也是模 p 的二次剩余/二次非剩余。对于 p 的倍数，规定它既不是模 p 的二次剩余，也不是模 p 的二次非剩余。

    这相当于把整数 1,2,3,...,p-1 （或者说是全部与 p 互素的整数）分成了两类。

    二次剩余和乘法关系非常密切，大家不妨先猜猜下面三个结论哪个最好证？

1.二次剩余乘以二次剩余的结果是二次剩余；

2.二次剩余乘以二次非剩余的结果是二次非剩余；

3.二次非剩余乘以二次非剩余的结果是二次剩余。

    这组结论非常神奇，两个数是不是二次剩余决定了它们的乘积是不是二次剩余。如果你的回答是第一个，那么你和大多数人想的一样...第一条结论的正确性是显然的，因为两个平方数的乘积还是平方数。

    后两条结论怎么证？其实说破了非常简单。先写下一列数 1,2,3,...,p-1 ，然后随便取一个二次剩余与它们相乘，乘积写在对应乘数的右边，然后把右边一列模 p 取余。举个例子，如果 p=7 ，取的二次剩余为 2 （ 2 是平方剩余，因为 2≡3^2(mod 7) ），那么两列数就是这样的：

 1   2

 2   4

 3   6

 4   1

 5   3

 6   5

    显然第二列数两两不等，因此第二列数是 1,2,3,...,p-1 的一个排列。于是可以立即得出，两列数含有的二次剩余个数一样多（都是 (p-1)/2 个）。我们刚刚证过，两个二次剩余的乘积还是二次剩余，所以第一列的二次剩余必然对应着第二列的二次剩余，这样就可知第一列的二次非剩余必然对应着第二列的二次非剩余。

    这就证明了第二条结论，二次剩余与二次非剩余的乘积一定是二次非剩余。

    现在，我们把刚才的乘数改为二次非剩余。例如 p=7 ，取的二次非剩余为 3 ，则同样可以得到两列数：

 1   3

 2   6

 3   2

 4   5

 5   1

 6   4

    第二列数仍然是 1,2,3,...,p-1 ，这样我们可以得出第一列的二次剩余和第二列的二次非剩余一样多（都是 (p-1)/2 个）。我们刚刚证过，二次剩余与二次非剩余的乘积一定是二次非剩余，所以第一列的二次剩余必然对应着第二列的二次非剩余，这样就可知第一列的二次非剩余必然对应着第二列的二次剩余。

    这就证明了第三条结论，两个二次非剩余的乘积一定是二次剩余。

    不过，把三句话说成一句话，靠的是勒让德符号。规定勒让德符号：

http://s13/mw690/0032UzSRzy6HS0qAQ444c&690

    其中 p 为任意奇素数， a 为任意与 p 互素的整数。勒让德符号也记作 (a|p) 。

    这样上面的三句话就可以用一个式子表示：

http://s8/mw690/0032UzSRzy6HS0B0yATc7&690

    另外，我们可以定义 (a|p)=0 ，如果 a 是 p 的倍数。这样这个式子仍然成立。后面我们会看到，使用勒让德符号表述某些结论非常方便。

    关于二次剩余有个非常帅的结论就是欧拉判别法。若 p 为奇素数， a 与 p 互素（其实不互素也行...），那么有：

http://s2/mw690/0032UzSRzy6HS3N9qz751&690

    若 a 与 p 不互素则显然两边都是 0 。下面只关注 a 与 p 互素的情况。首先，左边必然与 1 或 -1 同余，因为由费马小定理，左边的平方一定与 1 同余，若把左边记作 A ，则有 p 整除 A^2-1 即 (A+1)(A-1) ，所以 p 必整除 A+1,A-1 之一。

    然后，若右边等于 1 （也就是说 a 为模 p 的二次剩余），这个很容易说明。设 a≡x^2(mod p) ，则左边就是 x 的 p-1 次方，由费马小定理得左边与 1 同余。

    若右边等于 -1 （也就是说 a 为模 p 的非二次剩余），这个稍有点麻烦。我们考虑 1,2,3,...,p-1 这些数的乘积，也就是 (p-1)! ，由威尔逊定理得这个数与 -1 同余。然后，我们把它们按照乘积为 a 两两配对，这回跟当初证明威尔逊定理时差不多，不过因为乘积由 1 变成了 a ，所以不会有自己和自己配对的情况（因为 a 不是模 p 的二次剩余），这回正好配出来 (p-1)/2 对，乘在一块就是 a^[(p-1)/2] ，这个数与 -1 同余。

    对于右边等于 -1 的情况还有一种证法：考虑次数为 (p-1)/2 的同余方程 x^[(p-1)/2]≡1(mod p) ，因为 p 是素数，所以这个方程最多有 (p-1)/2 个两两不同余的解。又因为刚刚证过 (p-1)/2 个平方剩余都是这个方程的解，所以这个方程不可能再有别的解了。也就是说 a 是二次非剩余时 a^[(p-1)/2] 不可能与 1 同余，那就只能与 -1 同余了。

    这样，欧拉判别法就证完了。

    欧拉判别法不仅简单，而且有用。我们可以立即回答一个问题： -1 模哪些奇素数是二次剩余？也就是求一下 (-1|p) 的值。用常规方法不太好算，但是用欧拉判别法的话，很容易算出 -1 的某次方。讨论 (p-1)/2 的奇偶性就行了，得出结论，这是二次互反律的第一部分：

    设 p 为奇素数，则 -1 是模 p 的二次剩余，当且仅当 p 模 4 与 1 同余。

    写成表达式就是：

http://s16/mw690/0032UzSRzy6HSkplaEf4f&690

    接下来，我们再回答一个问题： 2 模哪些奇素数是二次剩余？求一下 (2|p) 的值。这下 2 的某次方不是那么好算了。不过，当时高斯却有个非常巧妙的方法：模仿费马小定理的证明。证明费马小定理时我们把 1,2,3,...,p-1 都乘了同一个数，这里为了凑出 (p-1)/2 次方，我们只取 (p-1)/2 个数。

    我们的思路就是这样的：

http://s8/mw690/0032UzSRzy6HSlo0f2fa7&690

    式子里面那个问号，可以写成我们想要的 2^[(p-1)/2] 。我们换一个角度看，对式子左边进行操作，把不超过 (p-1)/2 的数留下，剩下的数全部减去 p ，变成了一堆负数。把这些负号拿出来后，容易说明左边剩下的恰好是 1,2,3,...,(p-1)/2 的乘积（对应着左边原来的 p-1,2,p-3,4,p-5,6,... ）。和右边一约，我们就只关心左边到底拿出来了多少个负号，也就是说左边有多少个数超过了 (p-1)/2 。

    这个事好办，因为左边不超过 (p-1)/2 的数，也就是不超过 (p-1)/4 的正整数的个数，恰好是 (p-1)/4 取下整。左边一共有 (p-1)/2 个数，因此左边拿出负号的个数就是

http://s3/mw690/0032UzSRzy6HSlV9nRof2&690

    现在我们只需讨论出这个数的奇偶性就行了。为此我们对 p 模 8 分类讨论可得，这个数为偶数的充要条件是 p 模 8 余 1 或 7 。而这个数为偶数又是 (2|p)=1 的充要条件。于是我们得到了二次互反律的第二部分：

    设 p 为奇素数，则 2 是模 p 的二次剩余，当且仅当 p 模 8 与 1 或 7 同余。

    写成表达式就是：

http://s10/mw690/0032UzSRzy6HSmkkgqt89&690

    这篇文章先写到这，下篇介绍二次互反律的核心部分及证明，二次互反律是数论中非常漂亮的一个定理。