Log in to Mathigon

Google
Create New Account

Reset Password     

分享

改變語言

EnglishChineseTurkish

Send us Feedback

Please let us know if you have any feedback and suggestions, or if you find any errors and bugs in our content.

Sorry, your message couldn’t be submitted. Please try again!

Thanks for your feedback!

Reset Progress

Are you sure that you want to reset your progress, response and chat data for all sections in this course? This action cannot be undone.

詞彙表

Select one of the keywords on the left…

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

揭示所有步驟

我们在计算这些除数对时,会遇到一些只有第一对除数的数。一个例子是 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已经被删掉了. 再一次的,我们删掉它的倍数。
下一个素数是. 但是请注意,它的所有倍数都是已被删掉3的倍数。对于剩下的所有其它数也是一样的情形。因此所有这些剩下的数都必定是素数。

现在我们可以数数了,总共有个素数小于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. 显然出了什么问题!但是从步骤24都是绝对有效的,唯一的可能性是我们在步骤1中的初始假设是错误的。这意味着一定有无穷多个的素数。

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