更改语言

English中文DeutschRomânăTürkçe

登录到Mathigon

要么

新账户     重设密码     

整除和素数
因子和倍数
整除规律
素数(又叫质数)
素数的分布
最小公倍数
最大公约数

分享

重置进度

这将删除您在本课程中所有章节的进度和聊天数据，并且无法撤消！

词汇表

选择左侧的一个关键字...

整除和素数素数(又叫质数)

阅读时间: ~10 min

我们在计算这些除数对时，会遇到一些只有第一对除数的数。一个例子是 13 – 它只有 除数1和13自己。这些特殊的数被称为__素数__. 它们不能被拆成两个稍小的数的乘积。 某种程度上，它们成了“原子数”。

注意 1 自身 不是 一个素数, 所以首批的一些素数是 2, 3, 5, 7, 11, 13, …

任意不是素数的数都能被写成素数的乘积形式：我们只要不断的把它分解成更多的部分直到所有 因子都是素数。例如,

84
2
×
42
2
×
21
3
×
7
84
=
2
×
2
×
3
×
7

现在 2, 3 和 7 是素数而且不能再被分解了。2 × 2 × 3 × 7 被称为84的 质因式, 同时 2, 3 和 7 是它的 质因子. 注意一些素数，比如这里的2，可以在一个质因式 里出现多次。

每个整数都有一个质因式，但是没有两个数的质因式是一样的。更进一步，任意整数 都只有一种质因式写法 – 除非我们把素数不同顺序算成不同写法。这就是 算术基本定理(FTA-Fundamental Theorem of Arithmetic).

利用算术基本定理能够使许多数学问题变得简单多了: 我们做多个数的质因数分解时，我们先独立 分解一个个数来解决问题，这样通常会简单很多，然后把这些结果组合起来从而解决原来 的问题。

埃拉托色尼筛选法

结果, 很难确定一个数是否是素数: 你总是必须找到它 全部 的质因数, 随着数变大 而变得越难确定。 然而，希腊数学家 - 昔兰尼古城的埃拉托色尼想到了 一个简单的算法来找出100内的全部素数: 埃氏素数筛选法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
首先我们需要写下100内的所有整数
我们知道1不是素数，所以删掉它。
最小的素数是2. 任何2的倍数都不是素数，因为它有个因子2。所以我们能够删掉所有2的倍数。
在我们列表里下一个数是3 – 又是个素数. 所有3的倍数都不是素数，因为它有因子3, 所以我们也能删掉它们。
下一个数4, 已经被删掉了，所以我们继续下个数5: 它又是个素数, 同理我们删掉所有5的倍数。
下一个素数一定是, 因为6已经被删掉了. 再一次的，我们删掉它的倍数。
下一个素数是. 但是请注意，它的所有倍数都是。对于剩下的所有其它数也是一样的情形。因此所有这些剩下的数都必定是素数。

现在我们可以数数了，总共有个素数小于100。

有多少个素数？

当然我们能够用埃氏素数筛选法找更大的数素。在100到200间有21个素数, 200到300间 有16个素数，在400到500间有17个素数，而且10000到10100间只有11个。

素数看起来在不断的分散了，但是它们会终止吗？ 存在一个 最大 或 最后 的素数吗?

古希腊数学家亚历山大的欧几里德 第一个证明了存在无穷多个素数的， 通过下面的论证:

  1. 假设只有有限多个素数。
    P, P, P, P, P
  2. 让我们把它们全部相乘，得到一个非常大的数，我们把它称为N.
    N = P × P × P × P × P
  3. 现在我们思考下N + 1. 任何整除N的素数都不能整除N + 1. 而且因为所有整除N的素数都已经被找到了, 它们中也不存在能够整除N + 1的.
    P, P, P, P,
    P
    N
    P, P, P, P,
    P
    N + 1
  4. 根据算术基本定理我们知道N + 1必定有个质因数P’, 它不是N + 1自身，也不是其它新的能够整除N + 1的素数。
    P’ N + 1
  5. 在这两种情况下，我们找到了一个新的素数它却不在我们的原始列表中，但我们又假设了所有素数都在这个列表中。
  6. 显然出了什么问题！但是从步骤2–4都是绝对有效的，唯一的可能性是我们在步骤1中的初始假设是错误的。这意味着一定有无穷多个的素数。

欧几里得的解释是历史上第一个正式数学__证明__的例子 — 表明一个陈述一定是正确的 逻辑论证。这个例子通常被称为__反证法__：我们从一个假设开始，推断出一些不可能的事情，从而知道我们的假设一定是错误的。

Archie