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

第1節(jié)　二次剩余和非剩余

94

定理

如果我們?nèi)∧硞€數(shù)m作為模，那么，在數(shù)0，1，2，3，…，m-1中，當(dāng)m是偶數(shù)時，同余于平方數(shù)的數(shù)的個數(shù)不超過；當(dāng)m是奇數(shù)時，同余于平方數(shù)的數(shù)的個數(shù)不超過個。

證明

因為同余的數(shù)的平方數(shù)是彼此同余的，所以，任何同余于平方數(shù)的數(shù)也同時同余于某個小于m的數(shù)的平方。因此，考慮平方數(shù)0，1，4，9，…，（m-1）2的最小剩余就足夠了。顯然，（m-1）2≡1，（m-2）2≡22，（m-3）2≡32，…。因此，當(dāng)m是偶數(shù)時，平方數(shù)與，（-2）2與，…的最小剩余相同；當(dāng)m是奇數(shù)時，平方數(shù)與與，…是同余的。由此推出，當(dāng)m是偶數(shù)時，除了與平方數(shù)0，1，4，9，…，中的數(shù)同余的數(shù)之外，沒有其他的數(shù)同余于平方數(shù)；當(dāng)m是奇數(shù)時，任何與平方數(shù)同余的數(shù)一定和平方數(shù)0，1，4，9，…，中的某個數(shù)同余。因此，在前一種情況下，至多有個不同的最小剩余；在后一種情況下，至多有個不同的最小剩余。

例：對于模13，數(shù)0，1，2，3，…6的平方的最小剩余是0，1，4，9，3，12，10，并且在此之后，它們按照相反的順序，即10，12，3，…出現(xiàn)。因此，如果一個數(shù)不與這些剩余中的后一個同余，即如果它同余于2，5，6，7，8，11中的一個數(shù)，那么，它就不可能同余于一個平方數(shù)。

對于模15，我們可以求出下列剩余：0，1，4，9，1，10，6，4；在此之后，這些數(shù)以相反的順序出現(xiàn)。因此，在這里可以與某個平方數(shù)同余的剩余的個數(shù)小于，因為這樣的剩余只有0，1，4，6，9，10。數(shù)2，3，5，7，8，11，12，13，14以及任何同余于它們的數(shù)不可能對于模15同余于一個平方數(shù)。

95