146
通过基本定理和关于剩余-1和±2的定理，我们总是可以确定一个给定的数是另外一个给定的数的剩余还是非剩余。但是，为了能够将解答这个问题的必要的结论总结到一起，重新表述一下上面的结论还是很有必要的。
问题
给定两个任意的数P ，Q ；求Q 是P 的剩余还是非剩余。
解：1.令P ＝a α b β c γ …，其中a ，b ，c ，…是各不相等的取正号的质数（显然，我们必须考虑P 的绝对值） 。为了简洁，我们这里把x 是模y 的剩余或非剩余，简称为数x 对于数y 的关系 。那么，Q 对于P 的关系就取决于Q 对于a α 的关系，Q 对于b β 的关系，…（条目105） 。
2．为了能够确定Q 对于a α 的关系（以及Q 对于b β 的关系，…） ，有必要区分两种情况：
1）Q 能够被a 整除。令Q ＝Q ′a e ，其中Q ′不能被a 整除。那么，如果e ＝a 或者e ＞a ，我们就有Q R a α 。如果e 是奇数且e ＜a ，我们就有Q N a α ；而如果e 是偶数且e ＜a ，Q 对于a α 的关系就如同Q ′对于a α -e 的关系。这就简化为下面的情况：
2）Q 不能被a 整除。这时，又要区分两种情况：
①a ＝2。那么，当α ＝1时，我们总是有Q R a α ；当α ＝2时，Q 必须为4n ＋1的形式，并且，当α ＝3或α ＞3时，Q 就必须是8n ＋1的形式。如果这个条件成立，就有Q R a α 。
②a 是其他任意的质数。那么，Q 对于a α 的关系就如同Q 对于a 的关系（条目101） 。
3．我们按照如下的方式研究任意数Q 同质数a （a 是奇数） 之间的关系。当Q ＞a 时，以Q 对于模a 的最小正剩余 [15] 来代替Q 。这个剩余对于a 的关系和Q 对于a 的关系相同。
将Q 或替代它的数分解为质因数p ，p ′，p ″，…；当Q 为负数时，因数中还要加上-1。那么，显然，Q 对于a 的关系取决于质因数p ，p ′，p ″，…与a 的关系。也就是说，如果Q 的这些质因数中存在2m 个a 的非剩余，我们就有Q R a ；如果存在2m ＋1个a 的非剩余，我们就有Q N a 。同样容易发现的是，如果在因数p ，p ′，p ″，…中存在2，4，6个或者一般地，2k 个相等项，那么就可以安全地忽略。
4．如果-1和2在质因数p ，p ′，p ″，…中出现，那么它们对于a 的关系可以从条目108，112，113，114中确定。其他因数与a 之间的关系取决于a 对于这些因数的关系（基本定理和条目131中的定理） 。假设p 是其中一个因数，我们会发现（像前面讨论Q 和a 的关系，a 和p 的关系一样，这里Q 和a 分别比a 和p 更大） ，a 和p 之间的关系可以由条目108到114来确定（只要对于模p ，a 的最小剩余不含任何奇数的质因数即可） ，或者，a 和p 之间的关系取决于p 对于小于p 的质数的关系。对于其他的因数p ′，p ″，…，同样成立。通过继续做这种运算，我们最终将得到这样的一些数，它们之间的关系可以通过条目108到114中的定理来确定。通过举例我们更容易理解。
例：求数＋453对于数1236的关系。因为1236＝4×3×103，由上述讨论可知，＋453 R 4且＋453 R 3。现在，探索＋453对于103的关系。这个关系与＋41对于103的关系一样［41≡453（mod 103）］；或者与＋103对于41（基本定理） ，-20对于41的关系一样。因为-20＝-1×2×2×5，-1 R 41（条目108） ，并且＋5 R 41（因为41≡1，由基本定理可推出＋5是41的剩余） ，所以-20 R 41。由此推出，＋453 R 103，那么＋453 R 1236。实际上，我们可以得到453≡2972 （mod 1236）。
