§4. 素数[編集]
1.
整除の関係においては整数の符号を考える必要がないから,本節では文字は正の整数を表わすことにする.
整数はその約数の数からみれば,四つの種類に分かれる.
まず
は
以外のいかなる整数ででも割り切れるから,無限に多くの約数を有するものといわねばならない.
次に
は
以外に約数を有しない.
すなわちただ一つの約数を有する整数である.
と
とは別格の整数である.
なる整数
は少なくとも
と
との二つの約数を有する.
しかし或る数の約数というような語を制定したのは,
やその数自身以外の約数を目標としたのであるから,
の約数のうち,
と
とを除外して,その他の約数を真の約数ともいう.
さて
である整数
が真の約数を有しないときには,
を素数という.
例えば
,
,
,
,
,
などは素数である.
真の約数を有する整数を合成数という.
それは,かような整数は素数の積として表わすことができるからである.
例えば
,
,
,
,
などは合成数である.
よって符号を考えずにいえば,整数は次の四種類に分かれる.
 |
無限に多くの約数を有する.
|
(単数) |
ただ一つの約数を有する.
|
素数 |
真の約数を有しない.
|
合成数 |
真の約数を有する.
|
2.
次の定理は素数特有の性質を示すものである.
定理 1.8.
二つ以上の整数の積が或る素数で割り切れるならば, 因数のうち少なくとも一つがその素数で割り切れる.
が素数
で割り切れるときは,
または
が
で割り切れる.
したがって
または
または
が
で割り切れる.
因数が三つより多くても同様である(数学的帰納法).
定理 1.9.
合成数を素数の積に分解することができる.
かつその分解の結果はただ一様である(補遺 2 参照).
を素因数に分解したときに,因数の中の相等しいものを一つの巾[脚注:巾は羃の略.ベキと読む.]にまとめて

のような形に記すことができる.
ここでは
は相異なる 素数である.
このような素数巾への分解ももちろんただ一つである.
素因数への分解を用いるならば,整徐に関する問題が簡明に解決される.
命題 1.
を素数巾への分解とすれば,
のすべての約数は

において
,
,
とすることによって漏れなくまた重複なく得られる.
よって
の約数の数(
および
を含めて)は

である.
[証]
上記
が
の約数であることは明らかである.
それらの中に重複のないことは分解の一意性による.
約数に漏れのないことも同様である.
命題 2.
のすべての約数の和を
とすれば

(
は問題 1と同様).
[証]
問題 1によって

命題 3.
が二つずつ互いに素なるときには
因数の数はいくつでも同様.
命題 4.
のすべての約数の積は
に等しい.
[証]
を
の約数とし,
と置く.
をつぎつぎに
のすべての約数にすれば
も全体において
のすべての約数になる.
よって

故に

上記
のような
の約数
を互いに余約数という.
古代ギリシアの数学では或る整数
の約数(
を入れ,
を入れない)の和が
に等しいときに
を完全数(perfect number)と称した.
すなわち
が完全数であるとは
を意味するのである.
例えば

などがそれである.
同様の立場から
なる
を豊数(abundant number),
なる
を輸数(deficient number)といっていた.
命題 6.
はおのおの
と互いに素ならば,
と
とも互いに素である.
特に
ならば,
.
命題 7.
.
命題 8.
の中の少なくとも一つに含まれるすべての素因数を
とすれば

と置くことができる.
そうすれば
の最大公約数を
,最小公倍数を
とするとき,
は
のすべてにわたる積を示し,また
は
の最小の値,
は
の最大の値
を示すのである.
命題 9.
の最大公約数を
,また
の最大公約数を
,一般に
の中の
ずつの積の最大公約数を
,最後に
とすれば,おのおのの
は
で割り切れる.
もし
,(
)と置けば
は
で割り切れる.
また

で,
は
の最小公倍数に等しい.
[証]
問題 8の応用.
を大ききの順序に並べたものを
とすれば,
になる.
命題 10.
かりに
の最小公倍数を
で表わすことにする.
しからば

は最大公約数を表わすのである.
[証]
,
とすれば,問題は
![{\displaystyle {\text{Max}}[{\text{Min}}(\alpha _{1},\mu ),{\text{Min}}(\alpha _{2},\mu ),\dots ,{\text{Min}}(\alpha _{n},\mu )]={\text{Min}}[{\text{Max}}(\alpha _{1},\alpha _{2},\dots ,\alpha _{n}),\mu ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70b8b40e79cebd2a43a33c4ae639aebe39558f5b)
に帰する.
まず
ならば,左辺は
,右辺も同様である.
その他の場合には,例えば
とすれば,左辺の括弧
のうちで
でかつ
はもちろん
より大でないから,左辺は
に等しい.
また
だから右辺も
に等しい.
命題 11.
を
の最小公倍数とすれば,
,ただし
はそれぞれ
の約数で,二つずつ互いに素である.
[証]
を合成する各素数巾は
のうち少なくとも一つに含まれている.
に含まれるそれらの素数巾の積を
とし,
も同様に定める.
の二つ以上に含まれているものは,随意にそれらに対応する
のうちの一つへ入れる.
例えば,
,
ならば,
,
.
または
,
.
多項係数(補遺 3 参照)

に関しても同様である.
が
で割り切れないならば,多項係数は
で割り切れる(
の中にちょうど
で割り切れるものがあれば,
で割り切れる,
).
二項係数

が整数であることは,組合せの数としての意味から明白である.
故に連続する
個の正の整数の積は
で割り切れる.
これを直接に証明するために

とおいて,問題 13を応用することができる.
任意の素因数
が分子
と分母
とに含まれる数を比較すれば
![{\displaystyle \sum _{k=1}^{\infty }{\biggl [}{\frac {m}{p^{k}}}{\biggr ]}\geq \sum _{k=1}^{\infty }{\biggl [}{\frac {n}{p^{k}}}{\biggr ]}+\sum _{k=1}^{\infty }{\biggl [}{\frac {n'}{p^{k}}}{\biggr ]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b04ca96b44c3d819cbc828583747287ec738a681)
から
を得るから,これは明白である.
故に
は
で割り切れる.
命題 14.
既約分数
を部分分数に分解すること(
).
素数巾に分解して
とすれば,
(1)
ただし
で,
はただ一組に限る.
[証]
まず
に関する附帯条件を考えに入れないならば(補遺 4 参照),
(2)
すなわち

は定理 1.7によって,整数解を有する.
さて (2) においては
は正でも負でも,
に適当な整数を加え,または引いてそれを正の真分数に化することができる.
に関しても同様であるから,
に関する附帯条件を入れても (1) の解はある.
さてその一意性であるが,もしも同じ条件のもとにおいて

とすれば,引いて

を掛けて分母をはらえば

が
で割り切れることがわかる.
よって
は
で割り切れる(定理 1.6).
しかるに
,
,
.
故に
.
同様に
したがって
.
3.
素数が無隈にあることは古代ギリシアで知られていた.
次に掲げる証明は Euclid の幾何学原本に載っている.
4.
素数を求める方法として,古代ギリシアの数学で知られていたいわゆる Eratosthenesのふるい(篩)というのがある.
自然数
を大きさの順序に並べておいて,それをふるい分けて素数だけを残すのである.
まず
は素数でないから除外する.
その次の
は素数である.
から二つめずつの自然数にしるしを付けていけば,
の倍数が標記される.
それらはもちろん合成数であるからふるい落とされるべきものである.
さて
の次に残った
は素数である.
その
から三つめずつの自然数にしるしを付けていけば,
の倍数としてふるい落とされるべき数が標出される.
そのとき
の次に残った
は自己よりも小さい素数
の培数でないのであるから素数である.
から五つめずつの自然数にしるしを付けるとき,
の次に残っている
はすなわち
の次の素数である.
このような操作を続行して
なる素数に達したとすれば,
よりも小さい自然数でしるしの付いていないものは,みな素数である.
よりも小さい合成数は
よりも小さい或る素数の倍数でなければならないから,すでにしるしが付けられていなければならない.
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
|
(編注:底本での三本下線を、ここでは点線下線で表示した)
素数の表は千万までできている.
最も新しいのは「カーネギー研究所」(Carnegie Institute)から出した Lehmer の表である.
D. N. Lehmer |
: Factor table for the first ten millions (1909).
|
〃 |
: List of prime numbers from 1 to 10006721 (1914).
|