质数――高级概念

质数(又称素数)

质数只能被 1 或自己整除,并且一定要是大于 1 的整数。

例子:2、3、5、7、11 等等。

孪生质数

孪生质数就是相差2的质数对(连续两个都是质数的奇数)。

例子:(3,5)(5,7)(11,13) ……

是否有无穷多的孪生质数目前还是个未解的问题。

互质

公约数只是 1 或 −1 的两个整数(它们的最大公因数是 1 或 −1)

例子:15 和 28 是互质的,因为 15 的因数(1,3,5,15) 与 28 的因数 (1,2,4,7,14,28) 除了 1 之外是没有相同的。

梅森质数

形如 2n-1 的质数,在这种情况下,n 也是质数。

3、7、31、127 等都是梅森质数

当 n 为质数数时,2n-1 不一定是质数。例如,2047(=211-1)不是质数,虽然 11 是质数。2047 可以被 23 和 89 整除。

梅森质数是根据法国僧侣、神学家与数学家马兰·梅森(Marin Mersenne,公元 1588-1648)的名字命名的。

完全数

如果一个正整数等于它的个别真因数之和,这个数就叫完全数。一个数的真因数是不等于它自己的因数。

例子:6(真因数:1、2、3)是完全数,因为 1+2+3=6。

例子:28(真因数:1、2、4、7、14)也是完全数,因为 1+2+4+7+14=28。

欧几里得证明了如果 2n-1 是个梅森质数,2n-1(2n-1) 便是个偶完全数。我们现在称这些数为欧几里得数。欧拉证明了所有偶完全数都可以用这个格式及一个正质数 n 来表达。例如,把 3、7 和 31 代入公式的 2n-1 项就得到 6、28 和 496 这三个完全数。

这个表列出了从 n=1 到 13 的结果,包括了前首五个完全数:

n 2n-1 2n-1(2n-1) 是完全数?
1 1 1 n 不是质数
2 3 6 n 是质数,2n-1 是质数
3 7 28 n 是质数,2n-1 是质数
4 15 120 n 不是质数
5 31 496 n 是质数,2n-1 是质数
6 63 2016 n 不是质数
7 127 8128 n 是质数,2n-1 是质数
8 到 10 …… …… 不是质数
11 2047 2096128 n 是质数,但 2n-1 不是质数
12 4095 8386560 n 不是质数
13 8191 33550336 n 是质数,2n-1 是质数

是否有无穷多的偶完全数是个还未解决的问题。

盈数(又称丰数,过剩数)

任何小于它所有个别真因数的和的正整数。

例子:12 是盈数,因为它的个别真因数是 1、2、3、4 和 6,而这些数的和是 16。

亏数(又称作缺数)

任何大于它所有个别真因数的和的正整数。

质数是亏数,因为它只有一个真因数:1。

所有可以写成 2n 的数都是亏数。

例子:32(=25)是亏数,因为它个别真因数的和是 31(1+2+4+8+16)。

并且,当 p 为质数以及 n 为正整数时, pn 便是亏数。

例子:35=243。

243 的真因数是 81、27、9、3 和 1。

这些因数的和是 121,小于 243。

同样,56=15625,15625 的因数是 1、5、25、125、625 和 3125。

这些数的和是 3906,小于 15625。

相亲数(又称亲和数、友爱数、友好数)

两个数,彼此的个别真因数的和与另一方相等。

例子:220 和 284 是相亲数,因为:

  • 220 的因数(不算本身)是 1、2、4、5、10、11、20、22、44、55、110。
    这些因数的和 = 284
  • 284 的因数(不算本身)是 1、2、4、71、142。
    这些因数的和 = 220。

威尔逊定理

当且仅当 n 为质数时,则 (n-1)!+1 是 n 的倍数:

(n-1)! ≡ -1 (mod n)

欧几里得的无穷质数证明

这个证明基于:若有最大的指数,则会导致谬误。

把质数顺序排列并以数字标记:P1 = 2、P2 = 3、P3 = 5 等等。假设只有 n个质数,最大的质数就是 Pn。我们现在把所有的质数相乘,然后把积加一,称这个数为 Q:

Q = (P1 × P2 × P3 × P4... × Pn) + 1

如果我们用 Q 除以任何的质数,余数都会是一,所以 Q 不能被任何的质数整除。

但是,我们知道只有两种正整数:质数或可以分解为质数的积的数。所以 Q 必然是质数或者可以被大于 Pn 的质数整除。

无论是哪个情形,都有大于 Pn 的质数。假设 Pn 是最大的质数与此矛盾,所以假设必然是错误的。就是说,没有最大的质数。

哥德巴赫猜想

任一大于或等于 6 的偶数都可以表示成二个奇质数的和。

哥德巴赫猜想是由普鲁士数字学家与分析家克里斯蒂安·哥德巴赫(公元 1690-1764)所提出。哥德巴赫曾经是俄罗斯皇家学院的数学教授和历史学家,也当过彼得大帝的私人教师并在沙皇的外交部任职。

哥德巴赫也猜想所有的奇数都是三个奇质数的和:维诺格拉多夫定理证明了,除了可能有穷个数的奇数以外,这对于所有的质数都是成立的。