第4章　二次同余方程
（第94～152条）

第1节　二次剩余和非剩余

94

定理

如果我们取某个数m作为模，那么，在数0，1，2，3，…，m-1中，当m是偶数时，同余于平方数的数的个数不超过；当m是奇数时，同余于平方数的数的个数不超过个。

证明

因为同余的数的平方数是彼此同余的，所以，任何同余于平方数的数也同时同余于某个小于m的数的平方。因此，考虑平方数0，1，4，9，…，（m-1）2的最小剩余就足够了。显然，（m-1）2≡1，（m-2）2≡22，（m-3）2≡32，…。因此，当m是偶数时，平方数与，（-2）2与，…的最小剩余相同；当m是奇数时，平方数与与，…是同余的。由此推出，当m是偶数时，除了与平方数0，1，4，9，…，中的数同余的数之外，没有其他的数同余于平方数；当m是奇数时，任何与平方数同余的数一定和平方数0，1，4，9，…，中的某个数同余。因此，在前一种情况下，至多有个不同的最小剩余；在后一种情况下，至多有个不同的最小剩余。

例：对于模13，数0，1，2，3，…6的平方的最小剩余是0，1，4，9，3，12，10，并且在此之后，它们按照相反的顺序，即10，12，3，…出现。因此，如果一个数不与这些剩余中的后一个同余，即如果它同余于2，5，6，7，8，11中的一个数，那么，它就不可能同余于一个平方数。

对于模15，我们可以求出下列剩余：0，1，4，9，1，10，6，4；在此之后，这些数以相反的顺序出现。因此，在这里可以与某个平方数同余的剩余的个数小于，因为这样的剩余只有0，1，4，6，9，10。数2，3，5，7，8，11，12，13，14以及任何同余于它们的数不可能对于模15同余于一个平方数。

95

那么，对于任意模，所有的数都能分成两类；一类包含了所有能与某个平方数同余的数；另一类包含了所有不能与之同余的数。我们把前一类数称为作为模的数的二次剩余^[1]，而把后一类数称为这个数的二次非剩余。当不会产生歧义时，我们简单地把它们分别称为“剩余”和“非剩余”。并且明显地，所有的数0，1，2，3，…，m-1都可以划分为这两类，因为我们把同余的数放在同一类。

再一次地，在这项研究中，我们从质数模开始，即使在没有提到时也默认模为质数。但是，我们必须把质数2排除在外，因而，我们只讨论奇质数。