第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是一个偶数，所以偶数指标的个数与奇数指标的个数相同，各有个，因而剩余和非剩余的个数也相同。

例：

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