329
将质数同合数区分开来，并且将合数分解成它们的质因数，这是算术中最重要和最有用的问题之一。它令数学界为之着迷，古代和当代的数学家都进行过这个问题的研究，所以这里我们再做长篇大论就未免多余。然而，我们必须承认，到目前为止被提出的方法，要么局限于特殊情况，要么过于复杂冗长，即使在著名数学家所构造的表内的数字（这些数字不需要精巧的方法） ，也令最熟练的计算者感到厌烦，而且这些方法几乎不适用于更大的数字。即使这些表格每个人都能得到，且事实上对于大多数情况来说足够用了，但我们仍希望它们继续拓展，以便训练有素的计算员从大数分解成因数的过程中获益，从而节省时间。而且，科学自身的崇高性也要求人们去探索解决这样优雅的著名问题的所有可能的方法。因此，我们并不怀疑以下两个方法。从我们长期的经验来看，它们是有效的、简洁的，一定能给数学爱好者们丰厚的回报。随着数字变大，任何 方法都会越来越冗长，这是这个问题本身的性质所决定的。尽管如此，按照下面的方法，随着数字的增大，计算的困难度增加得很慢，我们已经成功处理了7位数，8位数甚至更多位的数字，处理的速度超出了我们的预期。而以前的方法对最不知疲倦的计算员来说，所需的计算量也是难以忍受的。
在使用下面的方法之前，可以先用除法简化数字，我们用一些较小的质数——例如2，3，5，7，…，一直到19或比19大一点——来除所给的数。这是非常有用的，可以避免使用精密的人为的方法 [5] 。并且，当除法不成功时，第2种方法的应用可以充分利用由这些除法导出的剩余 。例如，如果我们对数314159265分解因数，两次成功除以3，再除以5和7之后，我们就得到314159265＝9×5×7×997331，那么，我们只要用更精密的方法研究数997331就可以了，它不能被11，13，17，19整除。类似地，给定数43429448，我们可以去掉因数8，再对商5428681应用更加精密的方法。
330
第1个方法的基础是这样一个定理：任何是数M 的二次剩余的正数或者负数，也是M 的任意因数的剩余。
每个人都知道，如果M 不能被小于 的质数整除，则M 一定是质数；但是，如果所有小于这个界限且整除M 的质数是p ，q ，…，那么，数M 仅由这些质数（或者是它们的方幂） 构成，或者还有另一个大于 的质数，这个质数可以通过M 尽可能多地被p ，q ，…整除得到。因此，如果我们把所有小于 的质数整体（不包括那些我们已知不能整除M 的数 ）记为Ω ，显然，求出包含在Ω 中的所有M 的质因数就足够了。现在，如果我们通过某种方式知道数r （不是平方数） 是M 的二次剩余，则以r 为非剩余的所有的质数都不可能是M 的因数；因此，我们可以从Ω 中去掉所有这种类型的质数（它们通常构成Ω 中一半的数） 。并且，如果知道另一个非平方数r ′是M 的剩余，我们就能从Ω 中剩下的数中排除掉那些以r ′为非剩余的数。如果剩余r 和r ′是相互独立的（只有在二者都是某些数的剩余时它们相互不独立——当r r ′是平方数时会发生这种情况） ，我们就能再一次把这些数去掉大约一半。如果我们还知道M 的其他剩余r ″，r ，…，它们中的每一个都和其他所有的相互独立 [6] ，我们可以对它们中的每一个分别进行类似的排除。那么，Ω 中的数的个数就会快速减少，直到所有的数都被排除，在这种情况下剩下的数就一定是一个质数。如果Ω 中的数还剩下几个（显然，M 中的所有质因数——如果存在这样的质因数的话，它们都会出现在其中） ，那么用剩下的数做除法就不再困难。对于一个不超过1000000的数，通常6到7次排除就够了；对于一个8位数或者9位数，9到10次排除一定足够。现在我们还剩下两件事要做：第一 ，求足够多的合适的剩余；第二 ，用最方便的方式做排除。但是，我们需要改变问题的讨论次序，因为第二个问题能为我们指出最合适的剩余是哪些。
331
在第4章中，我们用了大量的篇幅指出如何将以给定的r 作为剩余的质数（假设r 不能被平方数整除） 和以给定r 作为非剩余的质数区别开；也就是说，如何区分表达式x 2 -r 的因数和非因数。表达式x 2 -r 的因数都包含于形如r z ＋a ，r z ＋b ，…，或者4r z ＋a ，4r z ＋b ，…的式子中，x 2 -r 的非因数也都包含于类似的式子中。当r 是一个非常小的数时，借助于这些公式我们能够进行排除。例如，当r ＝-1时，就排除了所有形如4z ＋3的数；当r ＝2时，就排除了所有形如8z ＋3和8z ＋5的数。但是，由于我们并不总是一定能够求得像这样的数M 的剩余，并且当r 的值比较大时，这个公式的应用不太方便。如果我们有这样一张表，表中包含了足够多的不能被平方数整除的正的和负的数r ，那么排除的工作量就能够大大减少。这个表应当把以r 为剩余的质数同以r 为非剩余的质数分开。这样一张表可以按照我们之前描述的位于本书结尾的范例那样排布。但为了使其符合我们现在的目的，表上的质数（模） 应当延展到很大的数，如1000或者10000。如果把合数和负数列在最上面就更加方便了，但由第4章可知，这不是绝对必要的。如果这样来构造这张表，则它的用处最大：每个竖向的列是活动的，可以重新装在板或条上（像纳皮尔表一样） 。这样的话，那些在每种情况下必需的列，即那些对应于给定的数的剩余r ，r ′，r ″，…的列就可以分别考察了。如果把它们适当地 放在表格中由模构成的第1列旁边（将每个条中对应于第1列中同一个质数的位置，摆放在与这个质数同一直线的方向上，换句话说，就是放在同一水平线上） ，那么在做完Ω 对应于r ，r ′，r ″，…的排除之后，剩下的质数就一目了然了：它们是第1列中的相邻的条上都有横线的数。凡是相邻的条上是空白的质数都要去掉。下面的例子可以对此做较好的诠释。如果我们知道数-6，＋13，-14，＋17，＋37，-53是997331的剩余，那么就把第1列（在此情况下，要把第1列延续到数997，即小于 的最大的质数） 和最上面的数为-6，＋13，…的那些列结合起来。我们给出这张表的一部分：
通过观察表，在按照剩余-6，＋13，…做完排除后，在包含于这部分表的质数里 ，Ω 中只有数127剩下来。延伸到数997的完整表格显示，Ω 中没有其他的数剩下来。我们试一下，就会发现127确实能够整除997331。按照这种方式，我们发现这个数可以分解成质因数127×7853。
由这个例子我们知道，那些不是很大的剩余，或者至少可以分解成质因数的剩余是非常有用的。因为，这张表直接使用的数不超过每栏最上方列出的数，它间接使用的是只包含表中能够分解成因数的那些数。
332
我们将给出三种求给定的数M 的剩余的方法，但在解释这些方法之前，我想指出两条结论，当我们的剩余不太适合时，这两条结论将帮助我们确定更简单的剩余。第一 ，如果能够被平方数k 2 整除的数a k 2 （我们假设它与M 互质） 是M 的剩余，那么a 就也是它的剩余。因此，能够被大的平方数整除的剩余与小的剩余一样有用，并且对于下面的方法提供的所有剩余，应当立即去除平方因数。第二 ，如果有两个或者更多的剩余，它们的积也是剩余。将这条结论与上一条结论结合起来，只要这些剩余有大量的公约数，我们常常可以由几个不够简单的剩余推导出简单的剩余。因此，由很多不大的因数构成的剩余就非常有用了，我们还要把这些剩余立即分解为它们的因数。通过例子和频繁的使用，我们还可以更好地理解这些结论的力量。
1．对通过频繁实践变得熟练的人来说，最简单和最方便的方法在于把M ，或者更一般地，把M 的倍数分解为两部分，即k M ＝a ＋b （两部分都为正的，或者一个是正的，一个是负的） 。它们的乘积取负号就是M 的剩余；因为-a b ≡a 2 ≡b 2 （mod M ），因而-a b R M 。应当这样取数a ，b ，使得它们的乘积能够被大的平方数整除，且它们的商是比较小的数，或者至少能够被分解成比较小的因数。这不难做到。我们尤其要推荐的是，取a 是一个平方数，或者是平方数的2倍，3倍，…，它和M 的差是一个比较小的数，或者是一个能够分解成合适的因数的数。例如，997331＝9992 -2×5×67＝9942 ＋5×11×132 ＝2×7062 ＋3×17×32 ＝3×5752 ＋11×31×42 ＝3×5772 -7×13×42 ＝3×5782 -7×19×37＝11×2292 ＋2×3×5×29×42 ＝11×3012 ＋5×122 …。因此，我们得到以下剩余：2×5×67，-5×11，-2×3×17，-3×11×31，3×7×13，3×7×19×37，-2×3×5×11×29。最后一个分解产生的剩余-5×11前面已经有了。对于剩余-3×11×31，-2×3×5×11×29，我们可以替换为3×5×31，2×3×29，这是它们和-5×11相结合得到的。
2．第2和第3种方法是基于这样的事实：如果具有相同行列式M ，-M ，或者更一般地，±k M 的两个二元型（A ，B ，C ）（A ′，B ′，C ′），属于同一个族，那么数A A ′，A C ′，A ′C 就是k M 的剩余。这不难发现，因为其中一个型的特征数，比如说m ，也是另一个型的特征数，因而m A ，m C ，m A ′，m C ′都是k M 的剩余。因此，如果（a ，b ，a ′）是一个具有正的行列式M ，或者更一般地，是k M 的约化型，且（a ′，b ′，a ″）（a ″，b ″，a ）是它的周期中的型，那么它们一定和（a ，b ，a ′）等价，并一定属于同一个族。此外，数a a ′，a a ″，a a 就是M 的剩余。借助于条目187中的算法，我们可以计算出这个周期中大量的型。最简单的剩余通常是通过设a ＝1，然后去掉那些因数太大后得出的剩余。下面是行列式为997331，1994662的型（1，998，-1327）和（1，1412，-918）的周期中开始部分的一些型
因此，所有的数-1327，670，…都是数997331的剩余，去掉那些有太大因数的数，我们得到这些剩余：2×5×67，37，13，-17×83，-5×11×13，-2×3×17，-2×59，-17×53。我们在上面已经找到了剩余2×5×67和-5×11，其中-5×11是由13和-5×11×13结合起来得到的。
3．设C 是不同于主类的类，它具有负行列式-M ，或者更一般地，-k M ，并且设它的周期是2C ，3C ，…（条目307） 。那么，类2C ，4C ，…就属于主族；类3C ，5C ，…属于与C 相同的族。因此，如果（a ，b ，c ）是C 中（最简单） 的型，且（a ′，b ′，c ′）是这个周期中的某个类（例如，n C ） 中的任意一个型；那么，对应于n 是偶数或者奇数，a ′或者a a ′就是M 的剩余（在n 是偶数的情况下，c ′也是剩余；在n 是奇数的情况下，a c ′，c a ′和c c ′是剩余） 。当a 非常小时，尤其是当a ＝3时［当k M ≡2（mod 3）时这是可以的］ ，周期的计算，即它的类中最简单的型的计算是极其容易的。下面是包含型（3，1，332444）的类的周期的开始部分
在去掉那些没有用的剩余之后，我们得到剩余3×476，1027，1085，425，或者（去掉平方因数） ，3×7×17，13×79，5×7×31，17。如果我们明智地把这些剩余同上面找到的8个剩余相结合，就得到以下12个剩余：-2×3，13，-2×7，17，37，-53，-5×11，79，-83，-2×59，-2×5×31，2×5×67。前6个剩余与我们在条目331中使用过的剩余一样。如果我们愿意，还可以补充剩余19和-29，它们是我们在第1种情况中找到的，那里的其他剩余依赖于我们这里找到的剩余。
333
对一个给定的数M 进行因数分解的第2个方法，是基于对表达式 （mod M ）的值的讨论，以及基于下面的观察。
1．当M 是质数或者是奇质数（它不整除D ） 的幂时，对应于M 是包含于x 2 ＋D 的因数的型还是非因数的型中，-D 就是M 的剩余或者非剩余。在前一种情况下，表达式 就只有2个不同的值，它们相反。
2．当M 是合数，即它等于p p ′p ″…时，其中数p ，p ′，p ″，…是不同的奇质数（都不整除D ） 或者是这样的奇质数的幂，那么，只有当-D 是p ，p ′，p ″，…每个数的剩余时，即，当所有这些数包含于x 2 ＋D 的因数的型中时，它才是M 的剩余。现在，如果分别用±r ，±r ′，±r ″表示表达式 对于模p ，p ′，p ″，…的每个值，那么，通过推导对于p 同余于r ′或者-r ′的数，我们就得到了这个表达式对于模M 的所有的值。它们的个数就等于2 μ ，其中μ 是因数p p ′p ″…的个数。现在，如果这些值是R ，-R ，R ′，-R ′，R ″，…，我们立即能发现，对于所有的数p ，p ′，p ″，…，R ≡R ′。但是对于这些数，都没有R ≡-R ′。因此，M 就是数M 和R -R ′的最大公约数，且1是M 和R ＋R ′的最大公约数。既不相同也不相反的两个值，例如R 和R ′，对于p ，p ′，p ″…其中一个或几个数，一定是同余的，但不会对它们所有的数都同余。对于其他数，就有R ≡-R ′。因此，前面的数的乘积就是数M 和R -R ′的最大公约数，后面的数的乘积就是R 和R ＋R ′的最大公约数。由此推出，如果我们求出表达式 的各个值与某个给定值的差和M 的所有最大公约数，那么，它们全体就包含数1，p ，p ′，p ″，…以及这些数中的所有2个数的乘积，3个数的乘积，…。那么，以这种方式，我们可以由这个表达式的值求出数p ，p ′，p ″，…。
现在，由条目327中的方法我们把这些值归结为表达式 的值，这里分母n 与M 互质，但计算它们不是我们现在的目的。数M 与R -R ′（它们对应于 和 ）的最大公约数，显然也是数M 和n n ′（R -R ′）的最大公约数，也即是M 和m n ′-m n ′的最大公约数，因为后者对于模M 同余于n n ′（R -R ′）。
334
我们可以以两种方式把上面的观察应用于当前的问题：第1种方法不仅能判断给定的数M 是质数还是合数，而且，当M 是合数时，还能给出它的因数；第2种方法更好，因为它使得计算更快捷，但只有反复使用这个方法才能得到合数的因数。不过第2种方法可以将这些数和质数区分开。
1．我们首先确定M 的二次负剩余数-D 。为了这个目的，我们可以使用条目332.1和332.2中给出的方法。本质上，选择什么剩余是任意的，而且不像前面的方法，这里也不需要D 是一个很小的数。但是，当行列式为-D 的每个正常原始族中包含的二元型的类的个数较少时，计算过程就更短。因此，如果这些剩余出现的话，从条目303列举的65个剩余中取数就会比较有帮助。所以，对于M ＝997331，剩余-102就是上面给出的所有负剩余中最合适的。现在，求表达式 的不同的值。如果仅有2个（相反的值） ，M 就一定是质数或者质数幂，如果有许多个值，例如2 μ ，M 就包含μ 个质数或者质数幂。这些因数可以通过上个条目中的方法找到。我们可以直接判断这些因数是质数还是质数幂，但是求表达式 的值的方式会得到整除M 的质数。因为，如果M 能够被质数π 的平方整除，那么这个计算就一定能得出数M ＝a m 2 ＋2b m n ＋c n 2 的一个或多个表示，在这些表示里面数m ，n 的最大公约数是π （因为，在这种情况下，-D 也是 的剩余） 。但是，当不存在m ，n 有公约数的数M 的表示时，这就表明M 不能被平方数整除，因而，所有的数p ，p ′，p ″，…都是质数。
例：通过上面所给的方法，我们发现表达式 有4个值，它们与 的值相同，997331与3×1664-113×2824以及与3×1664＋113×2824（或与314120和324104） 的最大公约数，分别是7853和127，所以997331＝127×7853，与前面所得相同。
2．我们取负数-D 使得M 包含于表达式x 2 ＋D 的因数型中。本质上，选择这一类数中的哪一个是任意的，但是，使得在行列式为-D 的族中的类的个数尽可能少的这样的数最有利。找到这样的数并不困难，因为在任意个尝试过的数中，出现数M 是因数形式和非因数形式的个数差不多。因此，从条目303中的65个数开始尝试（从最大的数开始） ，只有当它们都不合适时（一般地，16384种情况中会发生一次） ，我们才继续尝试去找这样的数，即每个族中只包含两个类。这时，我们应当研究表达式 的值，并且，如果我们求出它的值，按照和前面相同的方式可以由它推导出M 的因数；但是，如果求不到这样的值，也就是说-D 是M 的非剩余，M 就一定既不是质数也不是质数幂。如果是这种情况，我们想要求出它们的因数，就必须对D 使用其他的值进行重复相同的运算，或者尝试其他的方法。
例如，我们发现997331包含于x 2 ＋1848，x 2 ＋1365，x 2 ＋1320的非因数的形式中，且包含于x 2 ＋840的因数形式中；从表达式 （mod 997331）的值，我们得到 ，并且由此我们可以推导出和前面一样的因数。更多的例子可以参考条目328，那里第1个例子证明了5248681＝307×17683，第2个例子证明了4272943是质数，第3个例子证明了997331一定包含不止一个质数。
本书的篇幅只允许我们介绍每种求因数的方法的基本原理，下次，我们再做更深入的讨论，并附上辅助表以及其他辅助工具。
[1] 为了简洁，我们把后面的讨论限定于常用的十进制体系，但这个讨论也可以轻松地拓展到其他情况。
[2] 罗伯特森（《关于循环十进制分数理论》，哲学学报，伦敦，1769年，第207页）通过在第1个数字和最后1个数字上面加一个点来表示周期的开始和结尾。我们认为这里没有这个必要。
[3] 这个分数是接近23的平方根的那些分数中的一个，在12位十进制小数中，超出部分少于7位。
[4] 为了简洁，我们把n 能够被p 整除和n 不能被p 整除的两种情况一起考虑；在后一种情况下，我们应当令v ＝0。
[5] 而且，一般来说，由于在任意给定的6个数中，几乎不存在不能被2，3，5，…，19中的某个质数整除的数。
[6] 如果任意个数r ，r ′，r ″，…的乘积是平方数，它们中的每个数，例如r ，就是任意这样的质数的剩余（它不能整除它们中的任意一个数），这些质数是其他的数r ′，r ″，…的剩余。因此，对于独立的剩余，它们中不存在2对，3对，…的乘积是平方数。
