第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）。

但是，一旦我们所检验的数稍微变大，这个判别法就基本没有用了，因为计算量太大。