第3节 合数是不是给定质数的剩余或非剩余的问题,取决于它的因数的性质
98
定理
质数p的两个二次剩余的乘积是剩余;一个剩余和一个非剩余的乘积是非剩余;最后,两个非剩余的乘积是剩余。
证明
1.令A,B为平方数a2,b2的剩余;即,A≡a2,B≡b2。那么,乘积AB就同余于数ab的平方,即,它是剩余。
2.当A是剩余,例如,A≡a2,且B是非剩余,乘积AB就是非剩余。因为,我们假设AB≡k2,且令表达式(mod p)的值同余于b。因此,我们就有a2B≡a2b2且B≡b2;即,与我们的假设相反,B是剩余。
另一个证明。取数1,2,3,…,p-1中的所有剩余(有个),把每个数乘以A,则所有的乘积都是二次剩余且彼此不同余。现在,如果将非剩余B乘以A,则乘积就不同余于我们上面已经得到的乘积中的任何一个。因而,如果它是一个二次剩余,我们就有个彼此不同余的剩余,并且它们中不包括0。这与条目96矛盾。
3.设A,B为非剩余。将数1,2,3,…,p-1中所有的剩余乘以A。这样,我们就得到了个彼此不同余的非剩余(参考第二部分),乘积AB不与它们中的任何一个同余。那么,如果它是非剩余,我们就得到了个彼此不同余的非剩余,这与条目96矛盾。证明完毕。
从上一章的原理可以轻易地推出这些定理。这是因为,剩余的指标总是偶数,非剩余的指标总是奇数。所以,两个剩余或两个非剩余的乘积的指标是偶数,因此这个乘积本身是剩余。
这两个证明方法都可以用来证明下面的定理:
当数a和b都是剩余或都是非剩余时,表达式(mod p)的值是剩余;当数a和b一个是剩余且另一个是非剩余时,该表达式的值是非剩余。
它们可以通过上面的定理来证明。
99
一般地,如果所有的因数都是剩余,或者因数中非剩余的个数为偶数,那么任意个数的因数之积是剩余;如果因数中非剩余的个数为奇数,那么这个乘积就是非剩余。因此,只要我们知道单个因数的情况就容易判断一个合数是不是剩余。这就是为什么我们在表2中只列出了质数。表的布置是这样的:表的最左边列出了模[2],表的最上边列出了连续质数,当连续质数中的一个数是某个模的剩余时,就在这个数所在的列与这个模所在的行相交的位置标上“-”;当一个质数是模的非剩余时,对应的位置就留空白。