第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]，表的最上邊列出了連續質數，當連續質數中的一個數是某個模的剩余時，就在這個數所在的列與這個模所在的行相交的位置標上“-”；當一個質數是模的非剩余時，對應的位置就留空白。