五二小说网

手机浏览器扫描二维码访问

01 如何不去考虑数 How Not to Think About Numbers（第6页）

因而它不是17的倍数。

但对于19，整除性测试给出了另一种结论：

拥有了这一组测试，你现在就可以检查不大于500的所有数的素性，因为232=529超过了500，因此19是你需要考虑的最大的素因数。

例如，为了确定247的性质，我们只需要检查它是否能被不大于13的素因数整除，因为下一个素数的平方，172=289，超过了247。

运用对13的测试，我们发现247→（24+28）=52→13，这是一个13的倍数（247=19×13）。

素数相乘可以得到无平方因数（square-free）的数，要想构造关于这些数的整除性测试，可以叠加并行其素数因子的整除性测试。

比如，对于42=2×3×7，一个数n能被42整除，当且仅当n可以通过2，3和7的三项整除性测试。

但是，对于那些有平方数因数的数，像9=32，则不能由此得到。

顺便说一句，9是n的因数当且仅当9也是n的各位数字之和的因数。

你也许会问：数千年以来，那些聪明的数学家们难道还没有想出更好、更精妙的检测素性的方法？答案是有的。

2002年，我们发现了一个相对快速的判断一个给定的数是否为素数的方法。

不过，如果给定的数恰好是一个合数，那么这个所谓的“AKS素性测试”

并不能给出该数的因数分解。

虽然原则上说，找到一个给定数的素因数的问题可以通过试错来解决，但实际操作中，这对于很大的整数依然难以实现。

正因为此，它构成了很多互联网加密方法的基础。

我们会在第4章回到这个话题。

在那之前，我们会在接下来的两章中更近距离地认识一下素数和因数分解。

[1]　这里的中文数字“六”

强调的是“六”

这个数本身的概念。

[2]　我国的自然数包含零，而本书的自然数不包含零。

[3]　1码等于3英尺等于36英寸。

[4]　或称因子、约数，英文也可以写作divisor。

[5]　英文也可以写作prime。

[6]　这里指的立方数从2的立方开始，因为1=13。

[7]　又称丰数或过剩数。

[8]　最近的例子是孪生素数猜想，传奇美籍华裔数学家张益唐在2013年取得重大进展，引起轰动。

[9]　又称埃氏筛或素数筛，简称筛法。

埃拉托斯特尼（公元前276—公元前194），古希腊数学家、地理学家。

[10]　当解释有关任意数的性质的时候，数学家们会用符号为讨论的对象赋予名称。

对于数，这些名字通常都是小写字母，如m和n；两个数的积m×n经常简写为mn。