第5節　給定的數是給定質數模的剩余或非剩余的一般判別法

106

從上面的討論可以看出，只要我們能夠確定一個給定的質數是另一個給定的質數模的剩余或者非剩余，其他所有的情況都可以化歸為這種情況。因此，我們必須努力對這種情況確立一套可靠的判別法。不過，在這么做之前，我們先證明從上一章推導出的一個判別法。雖然它幾乎沒有什么實際用途，但是因為它簡潔又普遍適用，這里還是要提一下。

不能被質數2m＋1整除的任意數A，對應于Am≡＋1或是≡-1（mod 2m＋1），分別是這個質數的剩余或非剩余。

因為，設在任意系統中a是對于模2m＋1數A的指標；當A是2m＋1的剩余時，a是偶數；當A是2m＋1的非剩余時，a是奇數。但是Am的指標是ma，即，對應于a是偶數或者奇數，它就同余于0或者同余于m（mod 2m）。在前一種情況下，Am≡＋1；在后一種情況下，Am≡-1（mod 2m＋1）（參考條目57和62）。

例：3是13的剩余，因為36≡1（mod 13）；2是13的非剩余，因為26≡-1（mod 13）。

但是，一旦我們所檢驗的數稍微變大，這個判別法就基本沒有用了，因為計算量太大。