文化伟人代表作图释书系:算术研究
上QQ阅读APP看书,第一时间看更新

第3节 合数是不是给定质数的剩余或非剩余的问题,取决于它的因数的性质

98

定理

质数p的两个二次剩余的乘积是剩余;一个剩余和一个非剩余的乘积是非剩余;最后,两个非剩余的乘积是剩余。

证明

1.令AB为平方数a2b2的剩余;即,Aa2Bb2。那么,乘积AB就同余于数ab的平方,即,它是剩余。

2.当A是剩余,例如,Aa2,且B是非剩余,乘积AB就是非剩余。因为,我们假设ABk2,且令表达式(mod p)的值同余于b。因此,我们就有a2Ba2b2Bb2;即,与我们的假设相反,B是剩余。

另一个证明。取数1,2,3,…,p-1中的所有剩余(有个),把每个数乘以A,则所有的乘积都是二次剩余且彼此不同余。现在,如果将非剩余B乘以A,则乘积就不同余于我们上面已经得到的乘积中的任何一个。因而,如果它是一个二次剩余,我们就有个彼此不同余的剩余,并且它们中不包括0。这与条目96矛盾。

3.设AB为非剩余。将数1,2,3,…,p-1中所有的剩余乘以A。这样,我们就得到了个彼此不同余的非剩余(参考第二部分),乘积AB不与它们中的任何一个同余。那么,如果它是非剩余,我们就得到了个彼此不同余的非剩余,这与条目96矛盾。证明完毕。

从上一章的原理可以轻易地推出这些定理。这是因为,剩余的指标总是偶数,非剩余的指标总是奇数。所以,两个剩余或两个非剩余的乘积的指标是偶数,因此这个乘积本身是剩余。

这两个证明方法都可以用来证明下面的定理:

当数ab都是剩余或都是非剩余时,表达式(mod p)的值是剩余;当数ab一个是剩余且另一个是非剩余时,该表达式的值是非剩余。

它们可以通过上面的定理来证明。

99

一般地,如果所有的因数都是剩余,或者因数中非剩余的个数为偶数,那么任意个数的因数之积是剩余;如果因数中非剩余的个数为奇数,那么这个乘积就是非剩余。因此,只要我们知道单个因数的情况就容易判断一个合数是不是剩余。这就是为什么我们在表2中只列出了质数。表的布置是这样的:表的最左边列出了模[2],表的最上边列出了连续质数,当连续质数中的一个数是某个模的剩余时,就在这个数所在的列与这个模所在的行相交的位置标上“-”;当一个质数是模的非剩余时,对应的位置就留空白。