319
关于同余方程x 2 ≡A （mod m ）（它等价于不定方程x 2 ≡A ＋m y ） ，在第四章（条目146） 我们已经讨论过它的可能性，似乎不需要进一步讨论了。然而，为了求出变量本身，我们在前面（条目152） 指出过，间接方法比直接方法好。如果m 是质数（其他情况可以轻松地化归为这种情况） ，我们为此可以使用指数表1（按照条目316的说明，结合表3） ，我们在条目60中已经一般性地说明了这一点。但这个方法局限于表的范围。因此，我们希望下面的具有一般性且简洁的方法可以令爱好算术的读者感到高兴。
首先，我们指出，只考虑x 的那些不大于 的值就足够了，因为其他的值对于模m 同余于这些值。对于x 的这样的值，y 的值一定包含于 和 的范围内。因此，在这里面的明显的方法是，对于包含于这个范围内的y 的每一个值（我们把它们的总体记为Ω ） ，我们计算A ＋m y （我们把它记为V ） ，并且我们只保留那些使得V 是平方数的值。当m 是一个小的数（比如小于40） ，那么试验的次数很少，不需要简便方法，但是，当m 比较大时，通过下面的排除法 ，就可以尽可能地减少计算量。
320
设E 是一个与m 互质的大于2的任意整数，它的所有不同的（对于模E 不同余的） 二次非剩余是a ，b ，c ，…；并且，设同余方程
A ＋m y ≡a ，A ＋m y ≡b ，A ＋m y ≡c ，…
对于模E 的根分别是α ，β ，γ ，…，它们都是正的且小于E 。设y 有这样一个值，它对于模E 同余于数α ，β ，γ ，…其中的一个数。那么，由此得到的V ＝A ＋m y 的值就同余于a ，b ，c ，…其中的一个，因而它是E 的非剩余，所以它不是平方数。因此，我们可以立即将Ω 中包含于形如E t ＋α ，E t ＋β ，E t ＋γ ，…中没有用的值排除掉，测试剩下的值就足够了，我们称它们的组合为Ω ′。在这个运算中，数E 可以称为排除数。
如果我们取另外一个合适的排除数E ′，以同样的方式我们可以求出和E 的不同的二次非剩余一样多的数α ′，β ′，γ ′，…；y 对于模E ′不能同余于这些数。现在，我们可以再一次从Ω ′中去掉形如E ′t ＋α ′，E ′t ＋β ′，E ′t ＋γ ′，…的所有的数。以这种方式，我们继续排除数，直到测试包含在Ω 中的数不再比做一次新的排除更加困难。
例：给定等式x 2 ＝22＋97y ，y 的值的范围就是从 。那么（由于值0显然是没有用的） ，Ω 就包含数1，2，3，…，24。对于E ＝3，它只有一个非剩余，a ＝2；所以α ＝1，且我们必须从Ω 中排除所有形如3t ＋1的数；Ω ′中剩下的数就是16个。类似地，对于E ＝4，我们有a ＝2，b ＝3，因而α ＝0，β ＝1；并且我们必须排除掉形如4t 和4t ＋1的数。剩下的8个数是2，3，6，11，14，15，18，23。那么，对于E ＝5，我们发现必须去掉形如5t 和5t ＋3的数，因而还剩下2，6，11，14。取E ＝6，就排除所有形如6t ＋1和6t ＋4的数，但是这些数已经被去掉过了（因为它们也是形如3t ＋1的数） 。取E ＝7，排除掉所有形如7t ＋2，7t ＋3，7t ＋5的数，还剩下6，11，14。如果我们用这些值代入y ，我们得到的V 值分别是604，1089，1380，其中只有第2个数是平方数，所以x ＝±33。
321
在使用排除数E 的运算中，从V 的值中（Ω 中对应的y 的值） 只是去掉了所有E 的二次非剩余的值，但是作为E 的剩余的值并没有去掉。很明显，如果是E 奇数，使用E 和使用2E 没有区别，因为在这种情况下E 和2E 有相同的剩余和非剩余。因此，如果我们依次取3，4，5，…作为排除数，那么我们可以省略不能被4整除的偶数6，10，14，…这些多余的数。并且，使用E 和E ′作为排除数的两个运算去掉了所有这样的V 的值，即同时是E 和E ′两者的非剩余以及它们其中之一的非剩余的那些值，而同时是E 和E ′两者的剩余的那些值就被留了下来。现在，由于在E 和E ′没有公约数的情况下，被去掉的数是乘积E E ′的所有非剩余，而留下来的数是乘积E E ′的剩余，显然，使用排除数E E ′和使用两个排除数E 和E ′的效果是一样的，所以使用排除数E E ′是多余的。因此，我们可以忽略所有能够分解成两个互质的因数的排除数，并且使用那些要么本身是质数（不能整除m ） ，要么是质数幂的排除数就足够了。最后，在使用以质数p 的幂p μ 作为排除数后，排除数p 和p v （v ＜μ ）就是多余的了。因为，使用排除数p μ 后，V 中留下的仅是它的剩余的那些值，一定不存在p 或者较低次幂p v 的非剩余。如果在p μ 之前使用p 和p v ，那么使用排除数p μ 时，显然只能去掉V 的这样的值：它们同时既是p （或者p v ） 的剩余，也是p μ 的非剩余。因此，我们只要取p μ 的这种非剩余作为a ，b ，c ，…就够了。
322
通过以下方式，对应于任意给定排除数E ，求数α ，β ，γ ，…的计算可以很大程度地被简化。设 ，…是同余方程m y ≡a ，m y ≡b ，m y ≡c ，…（mod E ）的根，k 是同余方程m y ≡-A 的根，那么， 。现在，如果有必要通过解这些同余方程求 ，…的方法就不比我们上面使用的方法简单；但求解这些同余方程并不是必须的。这是因为，如果E 是一个质数，m 是E 的二次剩余，由条目98可知， ，即表达式 （mod E ）的值是E 的不同的非剩余；因而，如果不考虑它们的排列次序（这个次序反正也是无关紧要的） ，它们就与α ，β ，γ ，…完全相同。如果其他假设不变，m 是E 的非剩余，那么数 ，…就与E 的所有二次剩余相同，0除外。如果E 是一个（奇） 质数的平方数p 2 ，且p 已经被用作排除数，那么根据上个条目，只要取以下这些数作为a ，b ，c ，…就足够了：它们是模p 的剩余中的模p 2 的非剩余，即数p ，2p ，3p ，…，p 2 -p （所有被p 整除且小于p 2 的数，0除外） 。因此，我们一定可以得到这些数作为数 …，只有次序不同。同理，如果我们在取过排除数p 和p 2 之后，再取E ＝p 3 ，那么，取模p 的各个非剩余和p 2 的乘积作为a ，b ，c ，…就足够了。因此，当m 是模p 的非剩余时， …就是同样的这些数；当m 是模p 的非剩余时，它们就是模p 的除0以外的每个剩余和p 2 的乘积。一般地，如果我们取任意一个质数幂作为E ，比如p μ ，且在此之前已经使用过所有比p μ 低的幂作为排除数，那么，当μ 是偶数时， …就是p μ -1 和所有小于p 的数（0除外） 的乘积；当μ 是奇数且m R p 时， …就是p μ -1 和所有模p 的非剩余中小于p 的数的乘积；当μ 是奇数且m N p 时， …就是p μ -1 和所有模p 的剩余中小于p 的数的乘积。如果E ＝4，且a ＝2，b ＝3，那么对应于m ≡1或者m ≡3（mod 4），我们就有2和3，或者2和1分别是 。如果在使用过排除数4之后，取E ＝8，我们就有α ＝5，那么对应于m ≡1，m ≡3，m ≡5，m ≡7（mod 8）， 就是5，7，1，13。一般地，如果E 是2的更高次幂，比方说2 μ ，并且所有的比2 μ 更低的幂都已经使用过了，当μ 是偶数时，我们应当令a ＝2 μ -1 ，b ＝3×2 μ -2 ，那么，我们就得到了 ，对应于m ＝1或m ＝3，分别有 或者 。但是，当μ 是奇数时，我们应当令a ＝5×2 μ -3 ，则对应于m ≡1，m ≡3，m ≡5，m ≡7（mod 8）， 就等于2 μ -3 分别与5，7，1，3的乘积。
不过，熟练的数学家会轻松地找到一种方法，在用足够的排除法计算出α ，β ，γ ，…之后，简单地 从Ω 中去掉那些没有用的y 的值即可。但是我们没有足够的篇幅讨论它以及其他简化计算的技巧了。
