算術の基本定理

算術の基本定理（さんじゅつのきほんていり、英: fundamental theorem of arithmetic）または素因数分解の一意性（そいんすうぶんかいのいちいせい、英: unique factorization theorem）は、「任意の正整数は、1 を除いて、一つまたはそれ以上の素数の積として（因子の順番の違いを除いて）ただ一通りに表すことができる」という初等整数論（算術）における定理である。 定理 ― 任意の正整数 n > 1 は一意的に素数の積に表される： n = p 1 n 1 p 2 n 2 ⋯ p k n k = ∏ i = 1 k p i n i {\displaystyle n=p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{k}^{n_{k}}=\prod _{i=1}^{k}p_{i}^{n_{i}}} ただし、 p1 < p2 < … < pk は素数、 ni は正の整数である。 例えば 120 は 2 × 2 × 2 × 3 × 5 と素因数分解され、素数の順序を無視して、これ以外の素数の積として表すことはできない。 算術の基本定理の主張が、任意の自然数 ≧2 について「素数の積に分解される（素因数分解の存在）」という主張と「素因数分解があれば一意に決まる（分解の一意性）」という主張の大きく 2 つの部分からなっていることに留意すべきである。なぜならば、分解の存在は比較的素直に示せるのに対して、一意性の証明はそれよりも多少高度な論証を要するからである。一意性の証明にはいくつかの方法があるが、以下の事実（ユークリッドの補題） 素数 p が 2 つの自然数 a, b の積 ab を割り切るならば、p は a または b のいずれか一方を割り切る。 — エウクレイデス、『原論』第7巻命題30 を用いることが多い。また、素数の積としての順番を考慮しないのは、自然数が積に関して交換法則と結合法則を満たすことによる。そして通常は見易さを考慮して、素因数を最も小さいものから順に並べる。 この定理の整数の場合への自然な一般化は「0 以外の任意の整数は、素数と単数の積として因子の順番の違いを除いて一意に表される」である（この意味において「整数に対して算術の基本定理が成立する」と言うことができる）。同様の主張はもっと一般の環などにおいても（成り立つか成り立たないかを考えることができるという意味で）意味を持つけれども、必ずしも成立はしない。 定理 ― 0 以外の整数 n ≠ 0 は一意的に単数と素数の積に表される： n = ε p 1 n 1 p 2 n 2 ⋯ p k n k = ε ∏ i = 1 k p i n i {\displaystyle n=\varepsilon p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{k}^{n_{k}}=\varepsilon \prod _{i=1}^{k}p_{i}^{n_{i}}} ただし、ε は単数 ±1、 0 < p1 < p2 < ... < pk は素数、 ni は正の整数である。 ユークリッドの『原論』の7巻に実質的な証明が書かれている。 すべて合成数は何らかの素数に割り切られる。 — エウクレイデス、『原論』第7巻命題31 すべての数は素数であるかまたは何らかの素数に割り切られる。 — エウクレイデス、『原論』第7巻命題32 完全な形での証明はガウスの『算術研究』におけるものが最初であると考えられている。それは現代的な言葉で書けば以下のようになる。 定理の反例となる「素数の積で表せないような自然数 ≧2 」の存在を仮定すると、自然数の整礎性により、そのような数には最小の数（最小の反例）があるはずである。定義より素数は既に素数の積に表されているので、最小の反例 n は合成数であり、適当な自然数 a ≠ 1, b ≠ 1 をとれば n = ab とできるが、a < n かつ b < n ゆえ、n の最小性から右辺の各因子 a, b は素数の積として表され、n も素数の積で表せることとなり、矛盾する。ゆえに、任意の自然数 ≧2 は素数の積に表される。 素数 p が自然数の積 ab を割り切るならば、p は a または b の少なくとも一方を割り切ることに注意しよう。この補題はユークリッドの補題と呼ばれる。 実際、p が a を割り切らないならば、p と a は互いに素であり、ユークリッドの互除法を用いて px + ay = 1 となる整数 x, y の存在が示される（この等式はベズーの等式と呼ばれる）。両辺に b を掛ければ pbx + aby = b が得られるが、仮定より左辺の p および ab は p で割り切れるから、p が b を割り切ることが示される。p が b を割り切らないときも同様にして a を割り切ることが示せる。 少なくとも 2 通りの「素数の積」として表すことができる自然数 ≧2 が存在すると仮定し、そのような自然数のうち最小のもの n が n = p1p2 ... pr = q1q2 ... qs と異なる「素数の積」に表されるとする。先の注意から p1 は q1, q2, ..., qs の少なくともいずれか 1 つを割り切るが、n の最小性から q1, q2, ..., qs に対してはいずれも素因数分解が一意であるので、p1 = qj となるような j が取れる (1 ≦ j ≦ s)。このとき、 n' = p2 ... pr = q1 ... qj−1qj+1 ... qs が異なる「素数の積」としての表示であるとすると n の最小性に反する（並べ替えて一致するならば、n に 2 通りの表示を考えたことに反する）。 素数は整数論の世界の原子のようなものだから、整数を素数の因子に分解すれば必ず同じ「原子」が検出されるのは、ほとんど自明なことのように思える。原子とは、分割不可能な要素だと定義されている。もし、整数の分解が2通りのやり方でできたとしたら、分解できないはずの原子を分割したことになってしまわないだろうか？しかし、ここで化学とのアナロジーですべて考えるのは、誤解のもとだ。 素因数分解の一意性がそんなに自明でないことを理解するために、ここで次のような整数の部分集合を考えてみよう。 1, 5, 9, 13, 17, 21, 25, 29, … 等々、これは、4の倍数に1を加えた形になる正の整数の全体である。こうした数同士を掛けても同じ性質が保たれるので、このタイプの数を同じタイプより小さな数を掛け合わせて合成することができる。((4m + 1)(4n + 1) = 4(4mn + m + n) + 1 だから 4n + 1 の形をした整数全体の集合は積という演算で閉じている。) そこで、ふつうの整数の世界で素数を考えたのと同様のやり方で、「擬素数」というものを定義しよう。擬素数とはこのタイプ数であって、同じタイプのより小さな数の積としては表せない数のことである。たとえば、9は擬素数である。上のリストを見てわかるように、9より小さな同じタイプの数は1と5であり、9はこれらの積では表せないからだ(もちろん 3 × 3 = 9 ではあるが3はリスト外の数である)。 このタイプの数も、必ず擬素数の積の形で表すことができるのは明らかである。しかし、これら擬素数がこの集合の「原子」に相当するにもかかわらず、ここでは少し奇妙なことが生じる。たとえば693は、693 = 9 × 77 = 21 × 33 と2つの異なる方法で分解できてしまう。ここで現れる4つの因数9, 21, 33および77は、すべてここでいう擬素数である。素因数分解の一意性は、このタイプの数の体系に関しては成立しないのである。 抽象代数学において、この定理をもっと一般の場合に「仮説」として持ち込むならば、定理の主張は「任意の 0 でない元は、素元および単元の積として一意的に表される」となるのが自然である（「素元」は素数の一般化であり、「単元」は考えている範囲の数の中に逆数があるということの一般化である）。ここで「仮説」としたのは、定理の主張が意味を持つ同様の代数系（環やモノイド）の中にも、算術の基本定理が成立しないものがあるからである。 例えば、すべての整数が成す集合において、1 および −1 は、それ自身は素数ではないけれども、整数の範囲で逆数を持つ（実際、自分自身が逆数になる）から、「整数の範囲でも算術の基本定理は成り立つ」というふうに言うことができる。ほかにもユークリッド整域や主イデアル整域ならば、このような形で算術の基本定理を一般化したものが成立する。一般に、算術の基本定理が成り立つ環を一意分解環という。 一般に、分解の一意性のほうは成り立ちにくい性質である。実際、ネーター環は素元分解を必ずもつが、一意分解環でないようなネーター環が多く存在することが知られている。