第2節　當模是質數時，小于模的剩余的個數等于非剩余的個數

96

如果我們取質數p作為模，則在數1，2，3，…，p-1中，一半是二次剩余，剩下的是非剩余；即，剩余有個，非剩余也有個。

容易證明所有的平方數1，4，9，…，都是彼此不同余的。因為，如果r2≡（r′）2（mod p），這里數r，r′不相等且均不大于，那么，可設r＞r′，得到（r-r′）（r＋r′）是正數并且能被p整除。但是兩個因數（r-r′）和（r＋r′）都小于p，因此假設不成立（參考條目13）。因此，在數1，2，3，…，p-1中有個二次剩余。不可能有比這更多個的二次剩余，因為，如果我們增加剩余0，就得到個二次剩余，但所有剩余的個數不能大于這個數。那么，剩下的數就是非剩余，它們的個數是。

因為0總是剩余，所以我們在研究中就排除0以及所有可以被模整除的數。這種情況本身是清楚的，討論它只會讓定理不再優雅。出于同樣的原因，我們也排除2是模的情況。

97

因為本章中要證明的很多結論可以從上一章的原理中推導出來，而且用不同的方法去發現相同的結論也無妨，我們就繼續指出這種聯系。容易證實的是，所有同余于平方數的數都有偶數指標，所有不同余于平方數的數都有奇數指標。并且，因為p-1是一個偶數，所以偶數指標的個數與奇數指標的個數相同，各有個，因而剩余和非剩余的個數也相同。

例：

且所有小于這些模的其他的數都是非剩余。