離散数学及び演習 講義7

素数，合成数

離散数学及び演習
講義 7 2014. 6. 5（木）n∈N （n＞1） は素数（prime number）である

 n の正の約数は 1 と n だけである
例： 2，3，5，7，11，13，…

n∈N （n＞1） は合成数（composite number）である


素数（教科書 pp.106-113）

n は素数でない

1 は素数でも合成数でもない
 正の約数の個数


1… 1個
素数… 2個
 合成数 … 3 個以上


教科書･･･野崎昭弘：離散系の数学、近代科学社

2定理

証明
n ∈N が合成数ならば，素数 p が存在して，p n かつ p｜n．

n ∈N が合成数ならば，素数 p が存在して，
p  n かつ p｜n．


すべての素数 p に対して，p n であるとき，p｜n でないならば，n は素数である．
n を割り切る素数のうち最小のものを p とする．
p｜n だから，q∈N が存在して，n＝q・p．
n は合成数だから，q＞1．
ゆえに，素数 p’ が存在して，p’｜q．
p’＞0，q＞0 だから，定理から，p’  q．
一方，p’｜q，q｜n だから，p’｜n ．
ゆえに，p の定義から，p  p’．
したがって，p2  pp’  pq ＝n．すなわち，p  n ．

n 以下のどの素数でも割り切れない n は素数である．

例： n＝1999
n ＝44.7…
 44 以下のどの素数も1999を割り切らない ゆえに，1999は素数である．
34

Eratosthenes の篩（続き）

Eratosthenes の篩（ふるい）（sieve）
入力： n∈N
出力： n 以下のすべての素数 手順：

例： n＝50

（1） 2 から n までの自然数を並べる．

（1） 2 から n までの自然数を並べる．
（2） 2 に○印を付け，2 以外の 2 のすべての倍数に×印を付ける．
（3） 印が付いていない最小の数を p とする．
（4） p  n ならば，次の操作 a），b）を繰り返す．
a） p に○印を付け，p 以外の p のすべての倍数で，×印の付いていない数に×印を付ける．
b）印が付いていない最小の数を p とする．
（5） ×印が付いていない数が求める素数である．

52345678910111213141516171819202122232425

2627282930

313233343536373839

40

41424344454647484950
61離散数学及び演習 講義7

Eratosthenes の篩（続き２）

Eratosthenes の篩（続き３）例： n＝50例： n＝50（2） 2 に○印を付け，2 以外の 2 のすべての倍数に（3） 印が付いていない最小の数を p とする．

×印を付ける．
2○8×314×20×1526×32×274338×44×4950×7131925313794×10×16×5111722×28×2334×40×35394546×21336×12×18×714×20×1526×32×2743

38×44×4950×1324×30×1936×42×3141
4748×292 p＝ 3○89×25374×10×16×511176×12×18×22×28×2334×40×35394136×42×4546×4748×2133

2924×30×78

Eratosthenes の篩（続き４）

Eratosthenes の篩（続き５）n ＝7.2…
例： n＝50（4） p  n ならば，次の操作 a），b）を繰り返す．
a） p に○印を付け，p 以外の p のすべての倍数で，×印の付いていない数に×印を付ける．
72 p＝ ○3
○89××14×20×15×21×26×32×27×33×43

38×44×39×45×4950×1319253137

4×10×16×5
111722×28×2334×40×3546×n ＝7.2…
例： n＝50（4） p  n ならば，次の操作 a），b）を繰り返す．
b）印が付いていない最小の数を p とする．

6×12×18×714×20×15×21×26×32×27×33×4338×44×39×45×4950×1324×30×1936×42×31414748×292 p＝ ○3○89××25374 p＝ 5×1011×1617×6×12×18×22×28×2324×30×34×40×354136×42×46×4748×29910

Eratosthenes の篩（続き６）

Eratosthenes の篩（続き７）n ＝7.2…
例： n＝50（4） p  n ならば，次の操作 a），b）を繰り返す．
a） p に○印を付け，p 以外の p のすべての倍数で，×印の付いていない数に×印を付ける．
2○8×3○9×1914×20×15×21×25×3126×32×27×33×374338×44×39×45×4950×7134 p＝ ○5×1011×1617×6×12×18×22×28×232924×30×34×40×35×4136×42×46×4748×n ＝7.2…
例： n＝50（4） p  n ならば，次の操作 a），b）を繰り返す．
b）印が付いていない最小の数を p とする．
2○8×3
○9×1914×20×15×21×25×3126×32×27×33×374338×44×39×45×4950×

p＝ 713114 p＝ ○5×1011×1617×6×12×18×22×28×232924×30×34×40×35×4136×42×46×4748×122

離散数学及び演習 講義7

Eratosthenes の篩（続き８）

Eratosthenes の篩（続き９）n ＝7.2…
例： n＝50（4） p  n ならば，次の操作 a），b）を繰り返す．
a） p に○印を付け，p 以外の p のすべての倍数で，×印の付いていない数に×印を付ける．
2○8×3○9×1914×20×15×21×25×31

26×32×27×33×37
43

38×44×39×45×49×50×7
p＝ ○134×10×16×5○1122×28×232924×30×34×40×35×4136×42×46×4748×17

n ＝7.2…
例： n＝50（4） p  n ならば，次の操作 a），b）を繰り返す．
b）印が付いていない最小の数を p とする．

6×12×18×2○8×3○9×1914×20×15×21×25×31

26×32×27×33×37
4338×44×39×45×49×50×

7
p＝ ○
1345×
○10× p＝ 111617×6×12×18×22×28×23
2924×30×34×40×35×4136×42×46×47

48×1314

Eratosthenes の篩（続き９）Eratosthenes の篩（続き１０）

n ＝7.2…
例： n＝50（4） p  n ならば，次の操作 a），b）を繰り返す．

n ＝7.2…
例： n＝50（5） ×印が付いていない数が求める素数である．

2
○8×

3
○9×

1914×20×15×21×25×
3126×32×27×33×

37
4338×44×39×
45×49×50×

7○1345×○10× p＝ 111617×6×12×18×22×28×

23
2924×30×34×40×35×
4136×42×46×

47

48×

2
○8×3○9×1914×20×15×21×25×3126×32×27×33×374338×44×39×45×49×50×7○134×10×16×5○1122×28×232924×30×34×40×35×4136×42×46×4748×

176×12×18×1516

定理

証明

素数は無限に存在する．

素数は無限に存在する．


素数は有限個であると仮定して，矛盾を導く．

任意の n∈N に対して，n より大きい素数は存在しないと仮定する．
このとき， m＝n!＋1 とおくと，m＞n だから，m は合成数である．
ゆえに，素数 p（ n）が存在して，p｜m．
ところが，m は 2 以上 n 以下のどの自然数で割っても 1 だけ余る．
これは矛盾．
ゆえに，n より大きい素数は存在する．
n は任意だから，素数は無限に存在する．

17183

離散数学及び演習 講義7素数定理（1896年）

定理（素数の分布）

自然数 n より大きくない素数の個数をπ（n）とすると，十分大きな n に対して，
nπ（n）≒
log e nJ. Hadamard
C. J. de la Vallée-Poussin
あるいは，（仏，1865-1963） （ベルギー，1866-1963）
π（n） log e nlim
＝1n→∞nπ（n）／（n／logen）n 自然数の中に10001.16素数が含まれている割合
5000
1.14
 n＝1000 のとき
10000
1.13
 π（n）＝168
 n／logen＝144.76…
108
1.06

Chebysev（1850年）
任意の実数 x（＞1）に対して，x＜p＜2x となる素数 p が存在する．
 Dirichlet の算術級数定理（1837年）
a，n∈N に対して，gcd（a，n）＝1 ならば，p＝a＋kn （k∈N）という形の素数 p が無限に存在する．

P. L. Chebysev（露，1821-1864）

P. G. L. Dirichlet（露，1805-1859）

19

Mersenne 数（Mersenne number）


π（n）／（n／log e n）≒1.16

20

Mersenne 数（Mersenne number）

Mersenne 数
Mn＝2n－1 （n∈N） という形の数
M1 ＝ 21－1 ＝ 1
M2 ＝ 22－1 ＝ 3 … 素数
M3 ＝ 23－1 ＝ 7 … 素数
M4 ＝ 24－1 ＝ 15
M5 ＝ 25－1 ＝ 31 … 素数
M6 ＝ 26－1 ＝ 63
M7 ＝ 27－1 ＝ 127 … 素数：
（11,185,272桁）
M 37,156,667
M 42,643,801（12,837,064桁）
M 43,112,609（12,978,189桁）
M 57,885,161（17,425,170桁）
既知の Mersenne 素数は48個．


例：



M. Mersenne（仏，1588-1648）（2008. 9. 6，Elvenich, 独）（2009. 4.12，Strindmo, ノルウェー）（2008. 8.23，Smith, USA）
（2013. 1.25，Cooper，USA）

日本経済新聞2013. 2. 8GIMPS（Great Internet Mersenne Prime Search）（http://www.mersenne.org/）

大量のPCで分散計算，6万人以上のボランティア
1996年11月以来，Mersenne 素数14個を発見

2122定理証明
n∈N に対して，Mn＝2n－1 が素数ならば，n は素数である．

n∈N に対して，Mn＝2n－1 が素数ならば，n は素数である．

例：

＝ 22－1 ＝M2
3 … 素数M3 ＝ 23－1 ＝ 7 … 素数
M5 ＝ 25－1 ＝ 31 … 素数
M7 ＝ 27－1 ＝ 127 … 素数

n は合成数であると仮定する．
このとき，n＝k・s （ 1＜k＜n，k，s∈N ）とおける．
ゆえに， 2n－1＝ （2k）s－1＝ （2k－1）（2k（s－1）＋2k（s－2）＋…＋2k＋1）
2k（s－1）＋2k（s－2）＋…＋2k＋1 ＞1，2k－1＞1 だから，2n－1 は合成数となる．
これは矛盾．
ゆえに，n は素数である．

n が素数であっても， Mn が素数であるとは限らない．
n は合成数であると仮定して，矛盾を導く．

M11＝ 211－1 ＝2047＝23・89
23244

離散数学及び演習 講義7

Fermat 数（Fermat number）
定理

Fermat 数
n∈N に対して，2n＋1 が素数ならば，m∈N0 が存在して，n＝2m．

Fn＝22n＋1 （n∈N0） という形の数

例： F0 ＝ 220＋1 ＝
3 … 素数F1 ＝ 221＋1 ＝
5 … 素数F2 ＝ 222＋1 ＝
17 … 素数F3 ＝ 223＋1 ＝ 257 … 素数
P. de Fermat
F4 ＝ 224＋1 ＝65,537 … 素数
（仏，1601-1665）
5F5 ＝ 22 ＋1 ＝4,294,967,297＝641・6,700,417（Euler，1732年）
 F0，…，F4 以外の Fermat 素数は知られていない．
 F5，…，F11 の素因数分解は知られている．


F6 （1880年），F7 （1970年），F8 （1980年） F9 （1990年），F10 （1995年），F11 （1988年）

素因数が一つも知られていない最小の Fermat 合成数は F14

http://www.fermatsearch.org/2526証明

定理n∈N に対して，2n＋1 が素数ならば，m∈N0 が存在して，n＝2m．

任意の m，n∈N と任意の素数 p に対して，p｜mn ならば，p｜m または p｜n ．

2n＋1 は素数であるとする．
ここで，n＝k・s （ k＝2m，m 0，s は奇数 ）とおける．
1＝20・1，2＝21・1，3＝20・3，4＝22・1，5＝20・5，6＝21・3，…

ゆえに， 2n＋1＝ （2k）s＋1＝ （2k＋1）（2k（s－1）－2k（s－2）＋…－2k＋1）
2k＋1＞1，かつ，2n＋1 は素数だから，2n＋1＝2k＋1．
ゆえに，n＝k＝2m．

2728

証明

素因数分解の一意性定理

任意の m，n∈N と任意の素数 p に対して，p｜mn ならば，p｜m または p｜n．

（初等整数論の基本定理）
任意の n∈N は素数 p1，p2，…，pr （ p1 p2  …  pr ）に対して，n＝ p1・ p2・ …・ pr の形（素数の積の形）で一意に表せる．

p｜mn と仮定する．
さらに，p｜m， p｜n のいずれでもないと仮定する．
このとき，gcd（p，m）＝1．
ゆえに，定理から， p｜n．
 任意の p，m，n∈Z に対して，gcd（p，m）＝1 かつ p｜mnならば，p｜n．



自然数は素数の積の形で表すことができ，その表現は素数の順を除けば一意（ただ１通りだけ）である．

これは矛盾．
ゆえに， p｜m または p｜n．
2930

5

離散数学及び演習 講義7

素因数分解


証明
任意の n∈N は素数 p1，p2，…，pr （ p1 p2  …  pr ）に対して，n＝ p1・ p2・ …・ pr の形（素数の積の形）で一意に表せる．

n∈N の素因数分解（prime decomposition）
素数 p1，p2，…，pr に対して，n＝ p1・ p2・…・ pr

異なる素数 p1，p2，…，ps と e1，e2，…，es∈N0 に対して，n＝ p1e1 ・ p2e2 ・…・ ps esa-1） n が素数のとき．
r＝1， n＝p1となるから，明らか．
a-2） n が合成数のとき．
n に関する帰納法により示す．

例： p1＝2，p2＝3， p3＝5，p4＝7
a） 「n は素数の積の形で表せる」を示す．
b） 「n は素数の積の形で一意に表せる」を示す．

60＝22・31・51・70

n∈N の素因数（prime divisior）
n の約数である素数3132

証明（続き）

証明（続き２）

任意の n∈N は素数 p1，p2，…，pr （ p1 p2  …  pr ）に対して，n＝ p1・ p2・ …・ pr の形（素数の積の形）で一意に表せる．
任意の n∈N は素数 p1，p2，…，pr （ p1 p2  …  pr ）に対して，n＝ p1・ p2・ …・ pr の形（素数の積の形）で一意に表せる．
a） 「n＝ p1・ p2・ …・ pr の形（素数の積の形）で表せる」を示す．

b） 「n は素数の積の形で一意に表せる」を示す．

b） n＝ p1・ p2・ …・ pr （ p1 p2 … pr ），かつ，n＝ q1・ q2・ …・ qs （ q1 q2  … qs ） と仮定する．
n に関する帰納法により示す．
そこで，n’＜n となる任意の n’∈N に対して， n’ は素数の積の形で一意に表せると仮定する（帰納法の仮定）．
b-1） p1＝q1 のとき．
b-1-1）r＝s＝1 のとき．n＝p1＝q1 だから，n は素数の積の形で一意に表せる．
b-1-2）r＞1 または s＞1 のとき． n’＝ p2・ …・ pr ＝ q2・ …・ qs ∈N とおく．
このとき，n’＜n であるが， n’ は素数の積の形で一意に表せない．
これは帰納法の仮定に矛盾．
ゆえに，n は素数の積の形で一意に表せる．

a-2） n が合成数のとき．n に関する帰納法により示す．
そこで，n’＜n となる任意の n’∈N に対して， n’は素数の積の形で表せると仮定する（帰納法の仮定）．
n は合成数だから，定理から，素数 p  n ＜n が存在して，p｜n．
ゆえに，k∈N が存在して，n＝k・p．
k＜n だから，帰納法の仮定より，k＝p’1・ p’2・ …・ p’s とおける．
ゆえに，n＝k・p＝ p’1・ p’2・ …・ p’s ・p．
p’1， p’2，…， p’s ，p を小さい順に並べた列を p1，p2，…，pr とおけば，n＝ p1・ p2・ …・ pr （ p1  p2 …  pr ）．
33

34

証明（続き３）定理b） n＝ p1・ p2・ …・ pr （ p1 p2  …  pr ），かつ，n＝ q1・ q2・ …・ qs （ q1 q2  …  qs ） と仮定する．
n’＜n となる任意の n’∈N に対して， n’ は素数の積の形で一意に表せると仮定する．
b-2） p1＜q1 のとき．
除法定理から，u，v∈N が存在して， q1＝u・ p1 ＋v （0 v＜ p1 ）．
q1 は素数だから，v＞0．
このとき，n＝ p1・ p2・ …・ pr ＝（u・ p1 ＋v） ・ q2・ …・ qs だから，p1（ p2・ …・ pr －u ・ q2・ …・ qs ）＝ v ・ q2・ …・ qs ．
両辺を m （∈N）とおくと，m＞0．
このとき，p1 は左辺の素因数分解における m の素因数である．
一方，v＜ p1 ＜ q1  q2  …  qs だから，p1 は右辺の素因数分解におけるm の素因数でない．
したがって，m は素数の積の形で一意に表せない．
ところが，0＜v＜ q1 だから，m＝ v ・ q2・ …・ qs ＜ q1・ q2・ …・ qs ＝n．
これは帰納法の仮定に矛盾．ゆえに，n は素数の積の形で一意に表せる．
b-3） p1＞q1 のとき．同様に証明できる．
35m，n∈N の素因数分解をそれぞれ
m ＝ p1e1 ・ p2e2 ・…・ pr er
n ＝ p1h1 ・ p2h2 ・…・ pr hrとすると，m｜n であるとき，かつそのときに限り，任意の i （1 i r）に対して，ei hi．



例： 10＝21・30・51・70
42＝21・31・50・71
60＝22・31・51・70
 10｜60

1  2，0  1，1 1，0 042｜60 でない1  2，0  1，0  1，1 036

6

離散数学及び演習 講義7証明

証明（続き）

m，n∈N の素因数分解をそれぞれ m ＝ p1e1 ・ p2e2 ・…・ pr er，
n＝ p1h1 ・ p2h2 ・…・ pr hr とすると，m｜n であるとき，かつそのときに限り，任意の i （1 i  r）に対して，ei hi．
 a） 「 m｜n ならば，任意の i に対して ei hi 」を示す．
 b） 「 任意の i に対して ei  hi ならば，m｜n 」を示す．
 a） 「 m｜n 」を仮定して，「任意の i に対して ei  hi 」を示す．
 「ある i に対して ei ＞ hi 」を仮定して，矛盾を導く．

m，n∈N の素因数分解をそれぞれ m ＝ p1e1 ・ p2e2 ・…・ pr er，
n＝ p1h1 ・ p2h2 ・…・ pr hr とすると，m｜n であるとき，かつそのときに限り，任意の i （1 i  r）に対して，ei hi．
 b） 「 任意の i に対して， ei  hi ならば，m｜n 」を示す．
d＝ p1h1－e1 ・ p2h2－ e2 ・…・ pr hr－er とおく．
b） 任意の i （1  i  r）に対して， ei  hi とする．
hi－ei∈N0 だから，d∈Z．
ゆえに，n＝d・m．
したがって， m｜n ．

d＝ p1h1－e1 ・ p2h2－ e2 ・…・ pr hr－er とおく．
a） m｜n とする．このとき，n／m＝d∈Z．
ある i （1  i  r）に対して， ei＞hi と仮定する．
このとき， d・ pi ei－ hi ＝p1h1－e1・…・pi－1hi－1－ ei－1・pi＋1hi＋1－ ei＋1・…・pr hr－er ．
ここで，両辺とも整数である．
ei－hi＞0 だから，pi は左辺の素因数であるが，右辺の素因数ではない．
すなわち，同じ整数が素数の積の形に一意に表せなく，矛盾．
ゆえに，任意の i に対して， ei  hi ．
3738定理証明

m，n∈N の素因数分解をそれぞれ
m ＝ p1e1 ・ p2e2 ・…・ pr er
n ＝ p1h1 ・ p2h2 ・…・ pr hrとすると，lcm（m，n）＝p1max{e1，h1}・p2max{e2，h2}・…・prmax{er，hr}
gcd（m，n）＝p1min{e1，h1}・p2min{e2，h2}・…・prmin{er，hr}m，n∈N の素因数分解をそれぞれ m ＝ p1e1 ・ p2e2 ・…・ pr er，
n ＝ p1h1 ・ p2h2 ・…・ pr hr とすると，lcm（m，n）＝p1max{e1，h1}・p2max{e2，h2}・…・prmax{er，hr}

例： 60＝22・31・51・70
42＝21・31・50・71
2 1 1 1 lcm（60，42）＝ 2 ・3 ・5 ・7 ＝ 420
110 0 gcd（60，42）＝ 2 ・3 ・5 ・7 ＝ 6a） 任意の i （1  i  r）に対して，ei， hi  max{ ei， hi }．
ゆえに，定理から，m｜c，かつ， n｜c．
したがって， c は m，n の公倍数である．

p1max{e1，h1}・p2max{e2，h2}・…・prmax{er，hr}＝c とおく．
 「c＝ lcm（m，n）」を示す．
 a） 「c は m，n の公倍数である」を示す．
 b） 「m， n の任意の公倍数 c’ に対して，c｜c’」を示す．

3940

証明（続き）

まとめm，n∈N の素因数分解をそれぞれ m ＝ p1e1 ・ p2e2 ・…・ pr er，
n ＝ p1h1 ・ p2h2 ・…・ pr hr とすると，lcm（m，n）＝p1max{e1，h1}・p2max{e2，h2}・…・prmax{er，hr}

今回の講義p1max{e1，h1}・p2max{e2，h2}・…・prmax{er，hr}＝c とおく．
 「c＝ lcm（m，n）」を示す．
 b） 「m， n の任意の公倍数 c’ に対して，c｜c’」を示す．

次回の講義b） m， n の任意の公倍数を c’＝ p1f1 ・ p2 f2 ・…・ pr fr とする．
m｜c’，n｜c’ だから，任意の i （1 i  r）に対して，ei  fi， hi  fi ．
ゆえに，max{ ei，hi }  fi．
したがって， 定理から，c ｜c’ ．
すなわち，c＝ lcm（m，n）．
同様に，gcd（m，n）＝p1min{e1，h1}・p2min{e2，h2}・…・prmin{er，hr} を示せる．

（1限）1 次不定方程式（教科書 pp.117-127）（2限）合同式（教科書 pp.127-131）



次回の演習



今回の演習

41

素数なし
約数・倍数
427