第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排除在外，因而，我們只討論奇質數。