第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]，表的最上边列出了连续质数，当连续质数中的一个数是某个模的剩余时，就在这个数所在的列与这个模所在的行相交的位置标上“-”；当一个质数是模的非剩余时，对应的位置就留空白。