算術の基本定理

素因数分解の一意性はガウスの『算術研究』（1801年）で最初に証明された^{[注 1]}。ただし『算術研究』でガウスが基本定理と呼んだ定理は「平方剰余の相互法則」のことである^[1]。

算術の基本定理（さんじゅつのきほんていり、英: fundamental theorem of arithmetic）または素因数分解の一意性（そいんすうぶんかいのいちいせい、英: unique factorization theorem）は、「任意の正整数は、 $1$ を除いて、一つまたはそれ以上の素数の積として（因子の順番の違いを除いて）ただ一通りに表すことができる」^{[注 2]}という初等整数論（算術）における定理である^{[注 3]}。

定理 ― 任意の正整数 $n$ > 1 は一意的に素数の積に表される：

n=p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{k}^{n_{k}}=\prod _{i=1}^{k}p_{i}^{n_{i}}

ただし、 $p$ ₁ < $p$ ₂ < … < $p$ _k は素数、 $n$ _$i$ は正の整数である。

例えば $120$ は $2 \times 2 \times 2 \times 3 \times 5$ と素因数分解され、素数の順序を無視して、これ以外の素数の積として表すことはできない。

解説

算術の基本定理の主張が、任意の自然数 ≧2 について「素数の積に分解される（素因数分解の存在）」という主張と「素因数分解があれば一意に決まる（分解の一意性）」という主張の大きく 2 つの部分からなっていることに留意すべきである。なぜならば、分解の存在は比較的素直に示せるのに対して、一意性の証明はそれよりも多少高度な論証を要するからである。一意性の証明にはいくつかの方法があるが、以下の事実（ユークリッドの補題）

素数 $p$ が 2 つの自然数 $a, b$ の積 $ab$ を割り切るならば、 $p$ は $a$ または $b$ のいずれか一方を割り切る^{[注 4]}。 — エウクレイデス、『原論』第7巻命題30

を用いることが多い。また、素数の積としての順番を考慮しないのは、自然数が積に関して交換法則と結合法則を満たすことによる。そして通常は見易さを考慮して、素因数を最も小さいものから順に並べる。

この定理の整数の場合への自然な一般化は「 $0$ 以外の任意の整数は、素数と単数の積として因子の順番の違いを除いて一意に表される」である（この意味において「整数に対して算術の基本定理が成立する」と言うことができる）。同様の主張はもっと一般の環などにおいても（成り立つか成り立たないかを考えることができるという意味で）意味を持つけれども、必ずしも成立はしない。

定理 ― $0$ 以外の整数 $n$ ≠ $0$ は一意的に単数と素数の積に表される：

n=\varepsilon p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{k}^{n_{k}}=\varepsilon \prod _{i=1}^{k}p_{i}^{n_{i}}

ただし、 $ε$ は単数 $\pm1$ 、 $0$ < $p$ ₁ < $p$ ₂ < ... < $p$ _k は素数、 $n$ _$i$ は正の整数である。

証明

ユークリッドの『原論』の7巻に実質的な証明が書かれている。

すべて合成数は何らかの素数に割り切られる。 — エウクレイデス、『原論』第7巻命題31

すべての数は素数であるかまたは何らかの素数に割り切られる。 — エウクレイデス、『原論』第7巻命題32

完全な形での証明はガウスの『算術研究』におけるものが最初であると考えられている^{[注 1]}。それは現代的な言葉で書けば以下のようになる。

存在性の証明

定理の反例となる「素数の積で表せないような自然数 ≧2 」の存在を仮定すると、自然数の整礎性により、そのような数には最小の数（最小の反例）があるはずである。定義より素数は既に素数の積に表されているので、最小の反例 $n$ は合成数であり、適当な自然数 $a \neq 1$ , $b \neq 1$ をとれば $n = ab$ とできるが、 $a < n$ かつ $b < n$ ゆえ、 $n$ の最小性から右辺の各因子 $a, b$ は素数の積として表され、 $n$ も素数の積で表せることとなり、矛盾する。ゆえに、任意の自然数 ≧2 は素数の積に表される。

一意性

素数 $p$ が自然数の積 $ab$ を割り切るならば、 $p$ は $a$ または $b$ の少なくとも一方を割り切ることに注意しよう^{[注 5]}。この補題はユークリッドの補題と呼ばれる。

ユークリッドの補題の証明

実際、 $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 = p 1 p 2 ... p r = q 1 q 2 ... q s

と異なる「素数の積」に表されるとする。先の注意から $p 1$ は $q 1, q 2, ..., q s$ の少なくともいずれか 1 つを割り切るが、 $n$ の最小性から $q 1, q 2, ..., q s$ に対してはいずれも素因数分解が一意であるので、 $p 1 = q j$ となるような $j$ が取れる ( $1 ≦ j ≦ s$ )。このとき、

n' = p 2 ... p r = q 1 ... q j -1 q j +1 ... q s

が異なる「素数の積」としての表示であるとすると $n$ の最小性に反する（並べ替えて一致するならば、 $n$ に 2 通りの表示を考えたことに反する）^[4]。

なぜ素因数分解の一意性は、それほど自明ではないのか？

素数は整数論の世界の原子のようなものだから、整数を素数の因子に分解すれば必ず同じ「原子」が検出されるのは、ほとんど自明なことのように思える。原子とは、分割不可能な要素だと定義されている。もし、整数の分解が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は、すべてここでいう擬素数である。素因数分解の一意性は、このタイプの数の体系に関しては成立しないのである^[5]。

一般化

→詳細は「一意分解環」を参照

抽象代数学において、この定理をもっと一般の場合に「仮説」として持ち込むならば、定理の主張は「任意の $0$ でない元は、素元および単元の積として一意的に表される」となるのが自然である（「素元」は素数の一般化であり、「単元」は考えている範囲の数の中に逆数があるということの一般化である）。ここで「仮説」としたのは、定理の主張が意味を持つ同様の代数系（環やモノイド）の中にも、算術の基本定理が成立しないものがあるからである。

例えば、すべての整数が成す集合において、 $1$ および $-1$ は、それ自身は素数ではないけれども、整数の範囲で逆数を持つ（実際、自分自身が逆数になる）から、「整数の範囲でも算術の基本定理は成り立つ」というふうに言うことができる。ほかにもユークリッド整域や主イデアル整域ならば、このような形で算術の基本定理を一般化したものが成立する。一般に、算術の基本定理が成り立つ環を一意分解環という。

一般に、分解の一意性のほうは成り立ちにくい性質である。実際、ネーター環は素元分解を必ずもつが、一意分解環でないようなネーター環が多く存在することが知られている。

脚注

[脚注の使い方]

注

^ ^a ^b 【定理】どのような合成数もただ1通りの仕方で素因子に分解される (ガウス & 高瀬 1995, 第16条)。
^ (Hardy & Wright 2008) および (ハーディ & ライト 2012, pp. 2–4) は、定理 1: 「任意の正整数は、 $1$ を除いて、一つまたはそれ以上の素数の積に表される」("Every positive integer, except $1$ , is a product of one or more primes") と述べている（続く定理 2: 「その分解は一意である」とあわせて「基本定理」が構成される）。
^ $1$ を「 $0$ 個の素数の積」と見なすという規約を設けることも多い^[2]。そうすれば、この空積の規約を以って、 $1$ をも含めた全ての自然数について算術の基本定理が成り立つと述べることができる^[3]。このような規約は最大公約数の計算においてもしばしば有用である。^[要出典]
^ もし $a$ も $b$ も素数 $p$ で割り切れないならば、積 $ab$ もまた $p$ で割り切れない (ガウス & 高瀬 1995, 第14条)。
^ これが定理の証明において、鍵となる補題である。ガウス以前には長い間自明のことと見なされていた^[要出典]が、一般の代数体ではこの事実は成立しない。

出典

^ ガウス & 高瀬 1995, pp. 102, 497。
^ Nathanson 2000, p. 26.
^ Nathanson 2000, p. 26, Theorem 1.10 (Fundamental theorem of arithmetic).
^ 高木 1971, pp. 12f, 411f
^ スチュアート 2013, p. 113

参考文献

カール・フリードリヒ・ガウス『ガウス整数論』高瀬正仁訳、朝倉書店〈数学史叢書〉、1995年6月20日（原著1801年）。ISBN 4-254-11457-5。 - ラテン語原典からの日本語訳。
イアン・スチュアート著、沼田寛訳『無限をつかむ　イアン・スチュアートの数学物語』近代科学社、2013年8月。ISBN 978-4-7649-5017-7。
高木貞治『初等整数論講義』（第2版）共立出版、1971年10月。ISBN 978-4-320-01001-7。
Hardy, G. H.; Wright, E. M. (31 July 2008), Heath-Brown, Roger; Silverman, Joseph; Wiles, Andrew, eds., An Introduction to the Theory of Numbers (sixth ed.), USA: Oxford University Press, ISBN 978-0-19-921986-5
- G. H・ハーディ、E. M・ライト『数論入門 I』丸善出版、2012年1月。ISBN 978-4-621-06226-5。 - 原書第5版（1979年刊）の邦訳。
ハイベア・メンゲ編『ユークリッド原論』中村幸四郎・寺阪英孝・伊東俊太郎・池田美恵訳・解説、共立出版。 - 全13巻の最初の邦訳。
- （ハードカバー）1971年7月。ISBN 4-320-01072-8
- （縮刷版）1996年6月。ISBN 4-320-01513-4
- （追補版）2011年5月。ISBN 978-4-320-01965-2
ハイベア・メンゲ編『エウクレイデス全集』（全5巻）、東京大学出版会。 - 「エウクレイデス全集」の世界初の近代語訳。
- 『原論VII－X』第2巻、斎藤憲訳・解説、東京大学出版会、2015年8月。ISBN 978-4-13-065302-2。
Nathanson, M. B. (2000). Elementary Methods in Number Theory. Graduate Texts in Mathematics. 195. Springer-Verlag. ISBN 0-387-98912-9. MR1732941. Zbl 0953.11002

外部リンク

『分解定理』 - コトバンク
『整数論』 - コトバンク
『{{{2}}}』 - 高校数学の美しい物語
Proof of fundamental theorem of arithmetic - PlanetMath.（英語）
Weisstein, Eric W. "Abnormal number". mathworld.wolfram.com (英語).
Weisstein, Eric W. "Fundamental Theorem of Arithmetic". mathworld.wolfram.com (英語).
"Fundamental Theorem of Arithmetic" by Hector Zenil, Wolfram Demonstrations Project, 2007.（英語）

[Gauss1801.loc=16-1] 【定理】どのような合成数もただ1通りの仕方で素因子に分解される (ガウス & 高瀬 1995, 第16条)。

[3] (Hardy & Wright 2008) および (ハーディ & ライト 2012, pp. 2–4) は、定理 1: 「任意の正整数は、 $1$ を除いて、一つまたはそれ以上の素数の積に表される」("Every positive integer, except $1$ , is a product of one or more primes") と述べている（続く定理 2: 「その分解は一意である」とあわせて「基本定理」が構成される）。

[6] $1$ を「 $0$ 個の素数の積」と見なすという規約を設けることも多い^[2]。そうすれば、この空積の規約を以って、 $1$ をも含めた全ての自然数について算術の基本定理が成り立つと述べることができる^[3]。このような規約は最大公約数の計算においてもしばしば有用である。^[要出典]

[7] もし $a$ も $b$ も素数 $p$ で割り切れないならば、積 $ab$ もまた $p$ で割り切れない (ガウス & 高瀬 1995, 第14条)。

[8] これが定理の証明において、鍵となる補題である。ガウス以前には長い間自明のことと見なされていた^[要出典]が、一般の代数体ではこの事実は成立しない。

[2] ガウス & 高瀬 1995, pp. 102, 497。

[FOOTNOTENathanson200026-4] Nathanson 2000, p. 26.

[FOOTNOTENathanson200026Theorem_1.10_(Fundamental_theorem_of_arithmetic)-5] Nathanson 2000, p. 26, Theorem 1.10 (Fundamental theorem of arithmetic).

[9] 高木 1971, pp. 12f, 411f

[10] スチュアート 2013, p. 113

[注 1]

[1]

[注 2]

[注 3]

[注 4]

[注 5]

[4]

[5]

[2]

[3]

表話編歴被整除性に基づいた整数の集合
概要	素因数分解約数単約数約数関数素因数算術の基本定理
因数分解による分類	素数合成数半素数矩形数楔数平方因子をもたない整数多冪数累乗数アキレス数滑らかな数（英語版）ハミング数（英語版）粗い数（英語版）異常数（英語版）
約数和による分類	完全数概完全数準完全数倍積完全数 Hemiperfect number（英語版）ハイパー完全数超完全数単完全数（英語版）擬似完全数プラクティカル数エルデシュ・ニコラス数（英語版）
約数が多いもの	過剰数原始過剰数（英語版）高度過剰数超過剰数巨大過剰数高度合成数優高度合成数（英語版）不思議数
アリコット数列関連	アンタッチャブル数（英語版）友愛数 (友愛三数（英語版）) 社交数婚約数
位取り記法に基づくもの	Equidigital number（英語版） Extravagant number（英語版） Frugal number（英語版）ハーシャッド数 Polydivisible number（英語版）スミス数
その他	Arithmetic number（英語版）不足数 Friendly number（英語版） Solitary（英語版）サブライム数調和数デカルト数（英語版）タウ数超完全数

解説

証明