13第4章
4.1

素数と素因数分解の一意性

素数の定義

定義 4.1 整数 p が素数であるとは，p > 1 であって，1 < d < p をみたす約数 d をもたないものである．
素数でも 1 でも −1 でもない整数を合成数という（1, −1 は単数とよばれるが，いまは忘れちゃってもいい）． 一般に，整数 n 6= 0 に対して，1, −1, n, −n を n の自明な約数という． したがって，素数とは自明な約数しかもたない 1 より大きい整数のことである． この定義は，“約数” ということばを用いて述べられているが，以下のように “倍数”を用いて素数を特徴づけることもできる．
命題 4.2 整数 p が素数であるためには次が成り立つことが必要十分である; p > 1であって，a, b ∈ Z に対してその積 ab が p の倍数ならば，a または b は p の倍数である．
証明 必要性 p が素数であるとする． いま，p|ab を仮定する． a, p の最大公約数 d はp の正の約数だが，p が素数なので，d = p または d = 1 となる． d = p のとき，a が pの倍数であることは明らかである． 一方，d = 1 のときは，定理 2.6（または 3.5）より，ax + py = 1 (x, y ∈ Z) と表されるから，b = abx + pby は p の倍数となる．
十分性 d を p の約数とすると，p = cd (c ∈ Z) と書ける． もちろん p|cd だから，仮定
より p|c または p|d である． p|c ならば pk = c (k ∈ Z) と表されるから，p = cd = pkd，
よって kd = 1 より d = ±1 を得る． p|d のときは，pl = d (l ∈ Z) と書け，p = cd = cpl，よって cl = 1 だから c = ±1 すなわち d = ±p となる． 以上より，p は自明な約数しかもたないことが示されたから，p は素数である．
□
さて，素数の定義から直接導かれる性質として，任意の自然数 a > 1 が有限個の素数の積に書けることがあげられる． 実際，素数の積で書けない a > 1 があったとすると，その様な最小の自然数が存在する（最小値原理）． それをあらためて a とすれば，a はもちろん素数でないから，素数の定義より a = bc, 1 < b, c < a をみたす b, c ∈ N がとれるが，a の最小性より b, c は素数の積で書けるので，その積 a も書けることになり矛盾する．
自然数 a を素数の積に表すことを a の素因数分解といい，積に現れる素数を a の素因数または素因子という（a = 1 のときも 0 個の素因数をもつ分解と考えることにする）．
そして，素因数分解の仕方は順序を考えなければ一通りであることもよく知っているはずである． そのこともあわせて，定理としてまとめておく．

14
定理 4.3 (初等数論の基本定理) 1 より大きい任意の自然数 a は素数 p1 , · · · , pr の積

a = p1 · · · prとして表すことができ，順序を考えなければその表し方は一意的である． すなわち，二通りの素数の積a = p 1 · · · p r = q1 · · · qsに表されたとすると，r = s であって，さらに q1 , · · · , qr の番号をうまくとり換えれば p1 = q1 , · · · , pr = qr とできる． （より正確に書けば，{1, 2, · · · , r} 上の置換 σ で
pi = qσ(i) (i = 1, · · · , r) をみたすものが存在する．
）
証明 素因数分解が可能であることはすでに示した． 後半の表し方の一意性を示すために，二通りの素数の積として書ける自然数が存在するとして矛盾を導く． そのような最小の自然数を a とし，a = p1 · · · pr = q1 · · · qs を二通りの素数の積とする． p1 が素数でかつ p1 |q1 · · · qs なので，命題 4.2 を（何度か）使えば，p1 |qj をみたす j がとれることがわかる． 順序を入れ換えて j = 1 すなわち p1 |q1 であるとしてよい． ここでさらに q1 が素数であることから p1 = q1 を得る． したがって，p2 · · · pr = q2 · · · qs であって，仮定より，両辺の積の表し方は（順序を入れかえたとしても）同じにはならない． しかも，この積は a よりも小さいので，a の最小性に矛盾することになる．
□定理 4.3 の後半の主張はとくに素因数分解の一意性と呼ばれるが，その証明には，命題4.2 の形での素数の特徴づけが使われることに注意すべきである． 定理において，pi のうち同じものをまとめることで，

a = pe11 · · · perr

(p1 , · · · , pr は相異なる素数，ei ≥ 1)と表すことができる． さらに必要ならば，pi が素因数でない場合でも ei = 0 として積に含めることができる（このとき pei i = 1 に注意）． たとえば，20 = 22 · 51 = 22 · 30 · 51 ．
このような表し方も素因数分解とよぶことにする．
次の定理および系の証明は演習とする．
定理 4.4 自然数 a, b の素因数分解がa = pe11 · · · perr ,b = pf11 · · · pfrr

(p1 , · · · , pr は相異なる素数，ei , fi ≥ 0)で与えられたとき，次が成り立つ．

(1) a|b ⇐⇒ ei ≤ fi (i = 1, · · · , r)．
(2) di = min(ei , fi ) (i = 1, · · · , r) とおけば，gcd(a, b) = pd11 · · · pdr r ．
(3) gi = max(ei , fi ) (i = 1, · · · , r) とおけば，lcm(a, b) = pg11 · · · pgrr ．

15
系 4.5 自然数 a, b に対して d = gcd(a, b), m = lcm(a, b) とすると，ab = dm が成り立つ．

p を素数とする． 自然数 a に対して，pe |a であるが pe+1 ∤a であるような整数 e ≥ 0 がとれる． この e を vp (a) で表すと，a の素因数分解はY
a=pvp (a)p:素数と表すことができる． vp (−a) = vp (a), vp (0) = ∞ と定めることで，vp を Z 上の関数とみなすことができる (ただし，値として ∞ も許す)． この関数 vp を p 進付値という．

4.2

素数が無限個あること

次の定理は当たり前のようであるが，定理 4.3 との関連を考えると重要である．
定理 4.6 素数は無数に存在する．
以下において２通りの証明を与える（時間が許せば，講義でさらに別の証明も紹介する）． ひとつはユークリッドによる証明であり古代からよく知られていた方法，もうひとつは，オイラーによる示唆に富んだ方法である．
証明 [ユークリッド](古代) 素数が有限個しかないとして矛盾を導く． すべての素数をp1 , · · · , pr とし，M = p1 · · · pr + 1 とおく． 定理 4.3 より，M はある素数で割り切れるが，素数は p1 , · · · , pr のどれかだから，それを pi とする． このとき，1 = M − p1 · · · prが素数 pi の倍数となって矛盾する．
□証明 [オイラー](18 世紀) ここでも，素数は有限個しかなく，それらすべてが p1 , · · · , prであるとして矛盾を導くことにする． いま，等比数列の和の公式より，各素数 p = pi について∞X
1p1=1 =mpp−11− pm=0であり，これらの積をとれば

(♠)

p1
pr···
=p1 − 1pr − 1∞
X1m1pm =0 11!

∞
X1···
mp rm =0 rr!
=∞
X
m1 =0···∞X1.
r
pm1 · · · pmr
mr =0 1

最後の等式が正当化される理由は，絶対収束級数においては，和の順序をかってに換えたり，分配法則を自由に使って良いという性質があるからである（「微分積分」で教わったことを思い出そう . . . もし忘れちゃってたら微積の単位没収だぞ！）． ここで，p1 , · · · , pr がすべての素数であることから，定理 4.3 より，任意の自然数はmr
1 m2
pm
1 p2 · · · pr

(m1 , m2 , · · · , mr ≥ 0)

16の形に一通りに表されている． よって，(♠) の最右辺はすべての自然数の逆数和であり∞X
p1 · · · pr1=(p1 − 1) · · · (pr − 1) n=1 nとなるが，右辺は収束しない（これも微積でやったはず）から矛盾である．

4.3□ゼータ関数

オイラーは，自然数 n の代わりにベキ数 ns の逆数和を考え，無限級数

ζ(s) =∞X1
n=1n=1+s1
11+++ ···
2s 3s 4sが s > 1 のとき収束することに注目し，上の証明の手法を用いて，公式

ζ(s) =Yp1
1 − p−s(s > 1)を導いた． ここで，右辺は素数全体をわたる積でオイラー積と呼ばれている． さらに，sが正の偶数のときの ζ(s) の値

ζ(2) =π2,6ζ(4) =π4,90ζ(6) =π6945など . . .

を得ている (1730 年代)． ここに円周率 π が現れるのは，なんとも不思議である． その後，リーマンは s の動く範囲を複素数にまで広げ，複素関数としての ζ(s)（これをゼータ関数という）の性質を調べている． その目的はガウスが予想した素数定理の証明であったが，研究途上で有名な予想を提唱した (1859 年)．
予想 4.7 (リーマン予想 (Riemann Hypothesis)) ζ(s) = 0 をみたす実部が正の複1素数 s はすべて s = + it (t は実数) の形をしているであろう．
2
リーマン予想は 150 年以上経過した現在でも未解決の問題として残っている． なお，素数定理そのものはリーマン予想がなくても証明できることが知られている．
定理 4.8 (素数定理) 正の実数 x に対して，x 以下の素数の個数を π(x) とすると，limx→∞π(x) log x= 1.
xxで近似される． 証明は，アダマールとlog xド・ラ・ヴァレー・プーサンが独立に与えた (1896 年)． その方法は複素関数論（複素数上の微積分学）によるものだが，証明を書き下すだけの余白が，ここにもやっぱ無い．
すなわち，十分大きな x について π(x) は