1. No category

第 3 章 素数
3.1
3.1.1
素数と素因数分解
素数
定義 3.1 自然数 n に対し、±1 と ±n 以外の n の約数を 真の約数という。真の約数を持つ自然数を合成数、真の約数
を持たない自然数を 素数という。
すなわち、正の約数を３個以上持つ数が合成数。２個しか持たない数が素数である。素数は、その数自身を約数として
持つ数以外とは互いに素である。1 は合成数とも素数ともいわない。
例: 2、3、5、7、11、13、· · · は素数。4 = 2 × 2、6 = 2 × 3、8 = 2 × 2 × 2、9 = 3 × 3、10 = 2 × 5、· · · は合成数であ
る。（例終）
3.1.2
素数の性質
命題 3.2 整数 m1 、m2 、· · · 、mk の積 M = m1 m2 · · · mk が、素数 p で割り切れるならば、mi （i = 1, · · · , k ）のい
ずれかが p で割り切れる。
例 : m1 = 4、m2 = 3 とすると、M = m1 m2 = 12 は 素数 2 で割り切れる。このとき、m1 が 2 で割り切れている。
（例
終）
（命題 3.2 の証明） k についての帰納法。
k = 2 で成立すること : M = m1 m2 である。p が素数なので、(m1 , p) = 1 か (m1 , p) = p のいずれかである。もし、
(m1 , p) = 1 ならば、命題 2.11 より、m2 は p を約数として持つ。(m1 , p) = p ならば、m1 は p を約数として持つので、
これで主張は成立。
k > 2 で、k − 1 まで成立するなら k でも成立すること : k − 1 以下の個数の積について、主張が成立するならば、k 個
の積についての主張が成立することを示す。
M = m1 · · · mk−1 × mk
と分解して考えると、m1 · · · mk−1 または mk のどちらかが、p で割り切れる。m1 · · · mk−1 が p で割り切れる場合は、
帰納法の仮定より m1 、· · · 、mk−1 のいずれかが p で割り切れる。以上から m1 、· · · 、mk−1 、mk のいずれかが p で割
り切れることになり、主張は成立する。（証明終）
注意 : 命題 3.2 は、p が合成数のときは成立しない。例えば、上の例 m1 = 4、m2 = 3 で、M = m1 m2 = 12 は 6 で割
り切れるが、m1 も m2 も 6 を約数として持たない。
12
3.1.3
素因数分解
定理 3.3 合成数 n は、素数の積に分解される。また、その分解の仕方は素数の順序を除いて一意的である。すなわち、
次が成立する。
(i) 相異なる素数 p1 、p2 、· · · 、pk と、自然数 e1 、e2 、· · · 、ek により、n は、
n=
k
∏
pei i = pe11 pe22 · · · pekk
(3.1)
i=1
と表わされる。ただし、
∏
は、総和記号
∑
の乗法版、つまり、
k
∏
aj = a1 a2 · · · ak である。
j=1
(ii) (3.1) に現れる素数 p1 、· · · 、pk 、自然数 e1 、· · · 、ek · · · は順序を除いて一意的に定まる。
注意: 「順序を除いて一意的」ということの意味を説明しておく。例えば、自然数 24 は、
24 = 23 × 3 = 22 × 3 × 2 = 2 × 3 × 22 = 3 × 23
のように、いろいろな順序の積で表わすことができるが、どの場合も２が３個、３が１個という個数は変わらない。この
ように、24 の分解に現れる素数とその個数は常に不変であるということが、
「順序を除いて一意的」ということである。
（終）
定義 3.4 自然数 n に対して、(3.1) を n の素因数分解という。
以後 特に断らない限り、j を添字とする pj 、qj は相異なる素数で、ej 、fj は自然数であるとする。
それでは、定理 3.3 を証明する。
定理 3.3 の証明 : n についての帰納法を用いる。すなわち、
(i) 素数の積に分解できる。
(ii) 分解の仕方が順序を除いて一意である。
という主張が、
(I) 最小の合成数 4 について成立する。
(II) n > 4 の合成数に関し、
「n より小さい全ての合成数について (i)、(ii) が成立する。 =⇒ n について (i)、(ii) が成立する」
ことがいえる。
ということを示せばよい。
(I) 最初の合成数 4 については、4 = 2 × 2 = 22 なので主張 (i)、(ii) は成立する。
(II) n > 4 の合成数について、「n より小さい合成数に対し、定理の主張が成立するならば、n にも定理の主張が成立す
る」ことを示す。以下の (i)、(ii) を示せばよい。
(i) n が素数の積で表されること : n は合成数であるから、
n = ab,
1 < a < n,
1<b<n
となる自然数 a、b が存在する。a、b は素数もしくは合成数であるが、合成数ならば、帰納法の仮定より素数の積に表
わされるから、n は素数の積で表わされることになり、主張は成立する。
13
(ii) 分解の仕方が一意的であること : もし、
n=
k
∏
pei i =
i=1
l
∏
f
qj j ,
pi , (i = 1, · · · , k), qj , (j = 1, · · · , l) は素数
(3.2)
j=1
のように二通りに表わされたとすると、(3.2) により、n =
l
∏
f
qj j は p1 で割り切れることになるので、命題 3.2 より、
j=1
q1 、· · · 、ql のいずれかが p1 で割り切れる。例えば、q1 が p1 で割り切れるとすると、q1 は素数なので、p1 = q1 とな
る。ゆえに、(3.2) の両辺を p1 = q1 で割ると、
p1e1 −1 ×
k
∏
pei i = q1f1 −1 ×
i=2
l
∏
f
qj j
j=2
となる。この両辺は n より小さい自然数だから帰納法の仮定を満たす。よって、k = l で、これらの素数 p1 、p2 、· · ·
pk 、と q1 、q2 、· · · 、qk は順序を除いて等しい。したがって、k = l で、p1 、· · · 、pk と、q1 、· · · 、qk が順序を除いて等
しいことになる。（証明終）
系 3.5 整数 m が整数 m1 、m2 、· · · 、mk のいずれとも素であるならば、m はこれらの積 M = m1 m2 · · · mk とも互い
に素である。
例 : 3 は、7、10、11 のいずれとも互いに素である。このとき、3 と 7 × 10 × 11 = 770 は互いに素。（例終）
（系 3.5 の証明） d = (M, m) とする。d > 1 とすれば、定理 3.3 より、d の約数で素数であるものが存在する。それを p
とすれば、p は M = m1 m2 · · · mk の約数。よって、命題 3.2 により、p は m1 、· · · 、mk のいずれかの約数になる。一方、
p は m の約数でもあるので、m が mi （i = 1, · · · k ）のいずれとも素であるという仮定に反する。ゆえに、d = 1。
（証明終）
系 3.6 整数 m1 、m2 、· · · 、mk のどの二つも互いに素であるとき、整数 a がこれらのいずれでも割り切れるならば、a
は積 M = m1 m2 · · · mk で割り切れる。
例 : 3、4、5 は互いに素で 240 は、3、4、5 のいずれでも割り切れる。このとき、240 は 3 × 4 × 5 = 60 でも割り切れる。
（系 3.6 の証明） k に関する帰納法。
k = 2 で成り立つこと : m1 、m2 が互いに素であるとすると、命題 2.9 により、その最小公倍数は積 M = m1 m2 と等
しい。一方、a は、m1 、m2 で割り切れるので、これらの公倍数。したがって、命題 2.8 より a は最小公倍数の倍数に
なるので、k = 2 の場合は成立。
k > 2 のとき、k − 1 まで成立するなら k でも成立すること : 系 3.5 より、m1 、· · · 、mk−1 と mk は互いに素であり、
帰納法の仮定から、a は m1 · · · mk−1 で割り切れる。ゆえに、k = 2 の場合を m1 · · · mk−1 と mk に適用すると、a は
それらの積 m1 · · · mk−1 × mk でも割り切れることがわかる。よって、k > 2 の場合も成立。（証明終）
14
系 3.7 合成数 n の素因数分解を
n=
k
∏
e
pj j = pe11 pe22 · · · pekk
j=1
とすると、その正の約数の全体は、
k
∏
ϵ
(0 ≤ ϵj ≤ ej , (j = 1, · · · , k))
pjj
j=1
で与えられる。
（証明）
k
∏
ϵ
pjj
がn=
j=1
k
∏
e
pj j
の約数であることは明らかなので、n の約数が、すべて
j=1
k
∏
ϵ
pjj という形をしていること
j=1
をいう。自然数 d が、合成数 n の約数であるとする。このとき、
n = n′ d
(n′ ∈ N)
と表わせる。定理 3.3 を n′ 、d に適用すると、分解の一意性から、n′ 、d の素因数分解に現れる素因数は、どれも n の
素因数 pj （j = 1, · · · , k ）のいずれかと一致する。ゆえに、非負の整数 e′j 、ϵj （j = 1, · · · , k ）により、
n′ =
k
∏
e′
pj j ,
d=
j=1
k
∏
ϵ
pj j
j=1
′
と表わされ、n = n d において両辺の指数を比較すると、再び分解の一意性により、
ej = e′j + ϵj
(j = 1, · · · , k)
を得る。したがって、d は求める形をしている。（証明終）
例: 504 = 23 · 32 · 7 の素因数の全ての組み合わせを考えれば、504 の約数全体がわかる。すなわち、
20 · 30 · 70 = 1,
21 · 30 · 70 = 2,
22 · 30 · 70 = 4,
20 · 31 · 70 = 3,
21 · 31 · 70 = 6,
22 · 31 · 70 = 12,
20 · 32 · 70 = 9,
21 · 32 · 70 = 18,
22 · 32 · 70 = 36,
23 · 32 · 70 = 72,
20 · 30 · 71 = 7,
21 · 30 · 71 = 14,
22 · 30 · 71 = 28,
23 · 30 · 71 = 56,
20 · 31 · 71 = 21,
21 · 31 · 71 = 42,
20 · 32 · 71 = 63,
21 · 32 · 71 = 126,
23 · 30 · 70 = 8,
23 · 31 · 70 = 24,
22 · 31 · 71 = 84,
23 · 31 · 71 = 168,
22 · 32 · 71 = 252,
23 · 32 · 71 = 504
である。（例終）
系 3.8 合成数 a、b の素因数分解を合わせた相異なる素数を p1 、p2 、· · · 、pn とする。このとき、
a=
n
∏
pei i
i=1
b=
n
∏
pfi i
i=1
となる非負整数 ei ≥ 0、fi ≥ 0 をとると、
(a, b) =
n
∏
min{ei ,fi }
pi
,
i=1
[a, b] =
n
∏
max{ei ,fi }
pi
i=1
で表される。ただし、min{e, f } は、{e, f } の中の最小の数、max{e, f } は、{e, f } の中の最大の数。
15
例: 系を用いて、60 と 42 の最大公約数、最小公倍数を求めてみよう。60 = 22 · 3 · 5、42 = 2 · 3 · 7 と因数分解されるから、
60 = 22 · 31 · 51 · 70 ,
42 = 21 · 31 · 50 · 71
と考えると、
(60, 42) = 2min{2,1} · 3min{1,1} · 5min{1,0} · 7min{0,1} = 21 · 31 · 50 · 70 = 6
[60, 42] = 2max{2,1} · 3max{1,1} · 5max{1,0} · 7max{0,1} = 22 · 31 · 51 · 71 = 420
となる。（例終）
系 3.8 の証明 : 系 3.7 より、a、b の任意の正の公約数は、
k
∏
g
pj j
(0 ≤ gj ≤ ej , かつ 0 ≤ gj ≤ fj )
j=1
で与えられる。そのうち最大のものは、j = 1, · · · , k の全てにおいて、( ) の条件を満たす最大の gj （j = 1, · · · , k ）、す
なわち、
gj = min {ej , fj }
を選んだものである。すなわち、
(a, b) =
k
∏
min {ej ,fj }
pj
j=1
となる。
また、d = (a, b)、m = [a, b] としたとき、m = ab/d だったから、
e + f = max {e, f } + min {e, f }
を用いると、
m=
⇐⇒
k
∏
ab
e +f −min
=
pj j j
d
j=1
e + f − min {e, f } = max {e, f }
{ej ,fj }
=
k
∏
max {ej ,fj }
pj
j=1
がいえる。（証明終）
3.2
3.2.1
素数の見つけ方
素数は無限にある
前節の議論から、整数を考える上での素数は、化学での「原子」のような基本的な要素であるといえると思う。では、素
数は「どれくらい」あるのか。これが有限ならば、その組み合わせによってすべての整数が表されることになるのだが、
実は、そうはいかない。
定理 3.9 （ユークリッド）素数は無限に存在する。
（証明） 背理法。素数の数が有限で、その素数を p1 、p2 、· · · 、pn であるとする。このとき、
q := p1 p2 · · · pn + 1
とすると、これは自然数で、1 より大きいので、合成数か素数のいずれかであるが、これは、p1 、p2 、· · · 、pn のいずれ
で割っても 1 余るので合成数ではなく、帰納法の仮定より、素数でもない。よって、矛盾（証明終）
16
3.2.2
エラトステネスの篩
どの数が素数かを見つける初等的な方法として、次が知られている。たとえば、100 までの素数を求めたいとしよう。こ
のときは、まず、100 までの数を書いておく。
2
3
4
5
6
7
8
9
10
11
21
12
22
13
23
14 15
24 25
16
26
17
27
18
28
19
29
20
30
31
41
51
32
42
52
33
43
53
34 35
44 45
54 55
36
46
56
37
47
57
38
48
58
39
49
59
40
50
60
61
71
62
72
63
73
64 65
74 75
66
76
67
77
68
78
69
79
70
80
81
91
82
92
83
93
84 85
94 95
86
96
87
97
88
98
89
99
90
100
8
この表から、最小の素数である 2 を残し、その倍数を消してゆく
2
10
20
−
30
−
40
−
41 42
− 43 44
− 45 46
− 47 48
− 49
51 52
− 53 54
− 55 56
− 57 58
− 59
50
−
60
−
61 62
− 63 64
− 65 66
− 67 68
− 69
71 72
− 73 74
− 75 76
− 77 78
− 79
81 82
− 83 84
− 85 86
− 87 88
− 89
70
−
80
−
90
−
92
− 93
5
−
6
9
91
3
−
4
11 12
− 13 14
− 15 16
− 17 18
− 19
21 22
− 23 24
− 25 26
− 27 28
− 29
31 32
− 33 34
− 35 36
− 37 38
− 39
7
94
− 95 96
− 97 98
− 99
100
−
次に、3 を残し、その倍数を消してゆく。わかりやすいように、新たに消したところを = で書くことにする。
−
4
5 −
6
7
8 9=
14
− 15
= 16
− 17 18
− 19
10
20
−
21
= 22
− 23 24
− 25 26
− 27
= 28
− 29
31 32
− 33
= 34
− 35 36
− 37 38
− 39
=
41 42
− 43 44
− 45
= 46
− 47 48
− 49
30
−
40
−
50
−
51
= 52
− 53 54
− 55 56
− 57
= 58
− 59
61 62
− 63
= 64
− 65 66
− 67 68
− 69
=
60
−
70
−
11
2 3
12
− 13
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
−
17
4 を消しているので、次の数 5 を残し、その倍数を消してゆく。ここでも、新たに消した分を = で書くことにする。
−
4
5 −
6
7
8 −
9
14
− 15
− 16
− 17 18
− 19
10
20
−
21
− 22
− 23 24
− 25
− 26
− 27
− 28
− 29
31 32
− 33
− 34
− 35
− 36
− 37 38
− 39
−
41 42
− 43 44
− 45
− 46
− 47 48
− 49
30
−
40
−
50
−
51
− 52
− 53 54
− 55
= 56
− 57
− 58
− 59
61 62
− 63
− 64
− 65
= 66
− 67 68
− 69
−
60
−
70
−
2 3
12
− 13
11
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
−
以後、これを 7 について行い、11 について行い、· · · とすれば、最終的には、100 までの素数がすべて求まる。
問題 : この方法で、2 から 100 までの素数をすべて求めよ。
3.2.3
メルセンヌ数
最初にこんな素朴なアイディアから書き始めたことから想像できると思うが、
「ある数が素数であるか判定する」
「明示的
な式で素数を表す」ということは、非常に難しい。それならば、せめて、「素数がいそうなところ」を調べておきたい。
実は、「大きな素数」を見つけることは、最近の暗号において非常に重要になってきており、このようなところに「あた
り」をつけて手当たり次第にチェックする、ということが現在でも行われている。
定義 3.10 Mp := 2p − 1 (p : 整数) の形の数を メルセンヌ数という。
例: Mp （2 ≤ p ≤ 11）の値は
M2 = 22 − 1 = 3,
M7 = 27 − 1 = 127,
M3 = 23 − 1 = 7,
M4 = 24 − 1 = 15,
M8 = 28 − 1 = 255,
M5 = 25 − 1 = 31,
M9 = 29 − 1 = 511,
M6 = 26 − 1 = 63,
M10 = 210 − 1 = 1023,
M11 = 211 − 1 = 2047
となる。（例終）
この数に対し、次のことは直ちにわかる。
命題 3.11 Mp が素数ならば、p も素数。
（証明） p = ab とすると、
Mab = 2ab − 1 = (2a − 1){2a(b−1) − 2a(b−2) + · · · + 1}
となる。a > 1、b > 1 ならば、右辺のふたつの因数は両方とも 1 より大きいので、合成数になる。（証明終）
今の目的、つまり、「素数を見つける」というためには、この逆に興味がある。つまり、「p が素数 ⇒ Mp が素数」がい
えれば、とりあえず、好きなだけの数の素数ができる。しかし、一般にこれは成立しない。たとえば、
M11 = 211 − 1 = 2047 = 23 × 89
18
となってしまう。それでも、Mp という数の範囲内で、素数が見つけやすいというのも事実なので、ひとつの手段とし
て、素数に対するメルセンヌ数をチェックすることで、大きな素数を見つけるという試みが繰り返されている。実際、小
さい方の素数からチェックすると、
p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, · · ·
の場合が素数であることが知られている。Mp が素数になる p は、小さい順に p = 2、3、5、7、13、19、31、61、· · ·
となり、小さい順に 39 番目までわかっている。それが p = 13466917 だそうである。Mp が素数であるとき、それを メ
ルセンヌ素数という。現在分かっている最大のメルセンヌ素数は M43112609 だそうである（ 2008 年現在。）
19