第2节 当模是质数时,小于模的剩余的个数等于非剩余的个数

96

如果我们取质数p作为模,则在数1,2,3,…,p-1中,一半是二次剩余,剩下的是非剩余;即,剩余有个,非剩余也有个。

容易证明所有的平方数1,4,9,…,都是彼此不同余的。因为,如果r2≡(r′)2(mod p),这里数rr′不相等且均不大于,那么,可设rr′,得到(r-r′)(rr′)是正数并且能被p整除。但是两个因数(r-r′)和(rr′)都小于p,因此假设不成立(参考条目13)。因此,在数1,2,3,…,p-1中有个二次剩余。不可能有比这更多个的二次剩余,因为,如果我们增加剩余0,就得到个二次剩余,但所有剩余的个数不能大于这个数。那么,剩下的数就是非剩余,它们的个数是

因为0总是剩余,所以我们在研究中就排除0以及所有可以被模整除的数。这种情况本身是清楚的,讨论它只会让定理不再优雅。出于同样的原因,我们也排除2是模的情况。

97

因为本章中要证明的很多结论可以从上一章的原理中推导出来,而且用不同的方法去发现相同的结论也无妨,我们就继续指出这种联系。容易证实的是,所有同余于平方数的数都有偶数指标,所有不同余于平方数的数都有奇数指标。并且,因为p-1是一个偶数,所以偶数指标的个数与奇数指标的个数相同,各有个,因而剩余和非剩余的个数也相同。

例:

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