算術の基本定理

数学において、算術の基本定理は、一意因数分解定理や素因数分解定理とも呼ばれ、1より大きいすべての整数は、因数の順序まで素数の積として一意に表すことができると述べています。 ^{[3] [4] [5]}たとえば、

${\displaystyle 1200=2^{4}\cdot 3^{1}\cdot 5^{2}=(2\cdot 2\cdot 2\cdot 2)\cdot 3\cdot (5\cdot 5)=5\cdot 2\cdot 5\cdot 2\cdot 3\cdot 2\cdot 2=\ldots }$

この定理は、この例について 2 つのことを示しています。1 つ目は、1200 は素数の積として表すことができるということ、2 つ目は、どのように表しても、積には常に 2 が 4 つ、3 が 1 つ、5 が 2 つ含まれ、その他の素数は含まれないということです。

因数が素数であるという要件は必須です。合成数を含む因数分解は一意ではない可能性があります (たとえば、)。 ${\displaystyle 12=2\cdot 6=3\cdot 4}$

この定理は、1が素数ではない主な理由の1つです。1が素数であれば、素因数分解は一意ではなくなります。たとえば、${\displaystyle 2=2\cdot 1=2\cdot 1\cdot 1=\ldots }$

この定理は、一意因数分解領域と呼ばれる他の代数構造に一般化され、主イデアル領域、ユークリッド領域、および体上の多項式環を含む。しかし、この定理は代数的整数には当てはまらない。^{[6]この一意因数分解の失敗は、}フェルマーの最終定理の証明が困難な理由の1つである。代数的整数の環における一意因数分解の暗黙の使用は、フェルマーの声明からワイルズの証明までの358年間に書かれた多数の誤った証明の多くに誤りがある原因である。

基本定理は、ユークリッドの『原論』第 7 巻の命題 30、31、32 と、第 9 巻の命題 14 から導くことができます。

2 つの数を掛け合わせてある数を作り、その積を任意の素数で測定すると、元の数の 1 つも測定されます。

— ユークリッド『原論』第7巻、命題30

(現代の用語では、素数p が積ab を割り切れる場合、p はaまたはb のいずれか、あるいは両方を割り切れます。) 命題 30 はユークリッドの補題と呼ばれ、算術の基本定理を証明する鍵となります。

あらゆる合成数は何らかの素数によって測定されます。

— ユークリッド『原論』第7巻、命題31

(現代の用語では、1 より大きいすべての整数は、何らかの素数で均等に割り切れます。) 命題 31 は、無限降下によって直接証明されます。

あらゆる数は素数であるか、あるいは何らかの素数によって測定されます。

— ユークリッド『原論』第7巻、命題32

命題32は命題31から導かれ、分解が可能であることを証明します。

ある数が素数によって測定される最小の数である場合、その数は元々それを測定していた数以外の素数によって測定されることはありません。

— ユークリッド『原論』第 9 巻、命題 14

（現代の用語では、いくつかの素数の最小公倍数は、他の素数の倍数ではない。）第9巻の命題14は、第7巻の命題30から導かれ、分解が一意であることを部分的に証明しています。これは、アンドレ・ヴェイユによって批判的に指摘された点です。^[7]確かに、この命題では指数はすべて1に等しいため、一般的なケースについては何も述べられていません。

ユークリッドが素因数分解の存在への第一歩を踏み出したのに対し、カマール・アルディーン・アル・ファリスィーは最終段階を踏み出し^[8]、算術の基本定理を初めて提唱した^{[9] 。}

ガウスの『算術論』第16条は、モジュラー算術を用いた近世の記述と証明である。^[1]

1より大きいすべての正の整数nは、素数の累乗として正確に1つの方法で表すことができます。

${\displaystyle 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 は}正の整数です。この表現は、空積が 1 に等しい (空積はk = 0に対応) という規則により、1 を含むすべての正の整数に拡張されるのが一般的です。

この表現はnの標準表現^[10]、またはnの標準形^{[11] [12]}と呼ばれる。例えば、

999 = 3 ³ ×37、

1000 = 2 ³ ×5 ³、

1001 = 7×11×13。

因数p ⁰ = 1はnの値を変えずに挿入できる（例えば、1000 = 2 ³ ×3 ⁰ ×5 ³ ）。実際、任意の正の整数は、すべての正の素数の 無限積として一意に表すことができる。

${\displaystyle n=2^{n_{1}}3^{n_{2}}5^{n_{3}}7^{n_{4}}\cdots =\prod _{i=1}^{\infty }p_{i}^{n_{i}},}$

ここで、 n _iのうちの有限個は正の整数であり、その他はゼロです。

負の指数を許可すると、正の有理数の標準形が提供されます。

2 つの数値aとbの積、最大公約数(GCD)、最小公倍数(LCM)の標準表現は、aとb自体の標準表現で簡単に表現できます。

${\displaystyle {\begin{alignedat}{2}a\cdot b&=2^{a_{1}+b_{1}}3^{a_{2}+b_{2}}5^{a_{3}+b_{3}}7^{a_{4}+b_{4}}\cdots &&=\prod p_{i}^{a_{i}+b_{i}},\\\gcd(a,b)&=2^{\min(a_{1},b_{1})}3^{\min(a_{2},b_{2})}5^{\min(a_{3},b_{3})}7^{\min(a_{4},b_{4})}\cdots &&=\prod p_{i}^{\min(a_{i},b_{i})},\\\operatorname {lcm} (a,b)&=2^{\max(a_{1},b_{1})}3^{\max(a_{2},b_{2})}5^{\max(a_{3},b_{3})}7^{\max(a_{4},b_{4})}\cdots &&=\prod p_{i}^{\max(a_{i},b_{i})}.\end{alignedat}}}$

しかし、特に大きな数の整数因数分解は、積、GCD、LCM を計算するよりもはるかに困難です。そのため、これらの公式は実際にはあまり使用されません。

多くの算術関数は、標準表現を使用して定義されます。特に、加法関数と乗法関数の値は、素数の累乗の値によって決まります。

証明にはユークリッドの補題（ 『原論』第 VII 巻、30 節）が用いられます。素数が 2 つの整数の積を割り切る場合、その素数は少なくともこれらの整数の 1 つを割り切らなければなりません。

1より大きい整数はすべて素数か素数の積であることが示されなければなりません。まず、2は素数です。次に、強い帰納法によって、これが1より大きくnより小さいすべての数に当てはまると仮定します。nが素数の場合、証明することはこれ以上ありません。それ以外の場合、整数aとbがあり、ここでn = ab、かつ1 < a ≤ b < nです。帰納法の仮説により、a = p ₁ p ₂ ⋅⋅⋅ p _jおよびb = q ₁ q ₂ ⋅⋅⋅ q _kは素数の積です。しかし、n = ab = p ₁ p ₂ ⋅⋅⋅ p _j q ₁ q ₂ ⋅⋅⋅ q _kは素数の積です。

逆に、 2 つの異なる素因数分解を持つ整数があるとします。n をそのような最小の整数とし、n = p ₁ p ₂ ... p _j = q ₁ q ₂ ... q _kと書きます。ここで、p _iとq _{i は}それぞれ素数です。p _{1 は}q ₁ q ₂ ... q _kを割り切ることがわかります。したがって、ユークリッドの補題により、p _{1 は}何らかのq _{i を}割り切ります。一般性を失わずに、p _{1 は}q _{1 を}割り切るとします。p ₁とq _{1 は両方とも素数なので、} p ₁ = q ₁となります。 nの因数分解に戻ると、これら 2 つの因数を消去して、 p ₂ ... p _j = q ₂ ... q _kと結論付けることができます。これで、 nより確実に小さい整数の 2 つの異なる素因数分解が得られましたが、これはnの最小性と矛盾します。

算術の基本定理はユークリッドの補題を使わずに証明することもできます。^[13]以下の証明はユークリッドのオリジナルのユークリッド互除法に触発されたものです。

が 2 つの異なる方法で素数の積となる最小の正の整数であると仮定します。ちなみに、これはが存在する場合、より大きい合成数でなければならないことを意味します。ここで、 ${\displaystyle s}$${\displaystyle s}$${\displaystyle 1}$

${\displaystyle {\begin{aligned}s&=p_{1}p_{2}\cdots p_{m}\\&=q_{1}q_{2}\cdots q_{n}.\end{aligned}}}$

すべては、すべてと異なる必要があります。そうでない場合、 とすると、 sより小さく、2 つの異なる素因数分解を持つ正の整数が存在することになります。必要に応じて、2 つの因数分解を交換することによって、 と仮定することもできます。${\displaystyle p_{i}}$${\displaystyle q_{j}.}$${\displaystyle p_{i}=q_{j},}$${\displaystyle t=s/p_{i}=s/q_{j}}$${\displaystyle p_{1}<q_{1},}$

設定すると、また、となる ので 、 ${\displaystyle P=p_{2}\cdots p_{m}}$${\displaystyle Q=q_{2}\cdots q_{n},}$${\displaystyle s=p_{1}P=q_{1}Q.}$${\displaystyle p_{1}<q_{1},}$${\displaystyle Q<P.}$

${\displaystyle s-p_{1}Q=(q_{1}-p_{1})Q=p_{1}(P-Q)<s.}$

s未満の正の整数は一意に素因数分解されるものとされているため、はまたはQの因数分解で必ず発生します。 後者の場合は不可能です。Qはsより小さいため、一意に素因数分解される必要があり、のいずれとも異なるためです。 前者の場合も不可能です。が の約数である場合、は の約数でなければなりませんが、 と が異なる素数であるため、これは不可能です。 ${\displaystyle p_{1}}$${\displaystyle q_{1}-p_{1}}$${\displaystyle p_{1}}$${\displaystyle q_{j}.}$${\displaystyle p_{1}}$${\displaystyle q_{1}-p_{1},}$${\displaystyle q_{1},}$${\displaystyle p_{1}}$${\displaystyle q_{1}}$

したがって、1 つ以上の異なる素因数分解を持つ最小の整数は存在できません。すべての正の整数は、一意に因数分解される素数であるか、一意に素因数分解される合成数であるか、または整数 の場合のように、どの素因数にも因数分解されないかのいずれかでなければなりません。 ${\displaystyle 1}$

定理の最初の一般化は、ガウスの2番目のモノグラフである双二次相互性（1832年）に見られます。この論文では、現在ガウス整数環と呼ばれるもの、つまりaとbが整数であるすべての複素数a + biの集合が導入されました。これは現在では と表記されます。彼は、この環には4つの単位±1と± iがあり、ゼロでない非単位数は素数と合成数の2つのクラスに分類され、（順序を除いて）合成数は素数の積として一意に因数分解できることを示しました（順序と単位の乗算まで）。 ^[14] ${\displaystyle \mathbb {Z} [i].}$

同様に、1844 年に3 次相互法則の研究中に、アイゼンシュタインは1 の3乗根である環 を導入しました。これはアイゼンシュタイン整数の環であり、アイゼンシュタインはこれが 6 つの単位を持ち、一意に因数分解できることを証明しました。 ${\displaystyle \mathbb {Z} [\omega ]}$${\textstyle \omega ={\frac {-1+{\sqrt {-3}}}{2}},}$   ${\displaystyle \omega ^{3}=1}$${\displaystyle \pm 1,\pm \omega ,\pm \omega ^{2}}$

しかし、一意の因数分解が常に成り立つわけではないことも発見されました。例としては が挙げられます。この環では^[15]${\displaystyle \mathbb {Z} [{\sqrt {-5}}]}$

${\displaystyle 6=2\cdot 3=\left(1+{\sqrt {-5}}\right)\left(1-{\sqrt {-5}}\right).}$

このような例により、「素数」の概念は修正されました。 では、上記の因数が積として表せる場合、たとえば 2 = ab、aまたはbのいずれかが1 でなければならないことが証明できます。これが「素数」の従来の定義です。また、これらの因数がユークリッドの補題に従わないことも証明できます。たとえば、 2 は (1 + √ −5 ) と (1 − √ −5 ) の積 6 を割り切れますが、どちらも割り切れません。代数的整数論では、 2 はでは既約(自分自身または 1 でしか割り切れない)と呼ばれますが、 では素数ではありません(積を割り切れる場合は、因数の 1 つを割り切れる必要がある)。 の言及が必要なのは、 2 が素数であり では既約であるためです。これらの定義を使用すると、任意の整数領域で素数は既約でなければならないことが証明できます。ユークリッドの古典的な補題は、「整数の環では、すべての既約は素数である」と言い換えることができます。これは、およびでは当てはまりますが、${\displaystyle \mathbb {Z} \left[{\sqrt {-5}}\right]}$${\displaystyle \mathbb {Z} \left[{\sqrt {-5}}\right]}$${\displaystyle \mathbb {Z} \left[{\sqrt {-5}}\right]}$${\displaystyle \mathbb {Z} \left[{\sqrt {-5}}\right]}$${\displaystyle \mathbb {Z} .}$${\displaystyle \mathbb {Z} }$${\displaystyle \mathbb {Z} [i]}$${\displaystyle \mathbb {Z} [\omega ],}$${\displaystyle \mathbb {Z} [{\sqrt {-5}}].}$

既約数への因数分解が本質的に一意である環は、一意因数分解領域と呼ばれます。重要な例としては、整数上または体上の多項式環、ユークリッド領域、主イデアル領域などがあります。

1843 年にクンマーはイデアル数の概念を導入し、これはデデキント(1876)によってさらに発展して、環の特別な部分集合であるイデアルの現代理論となった。イデアルには乗法が定義され、イデアルが一意に因数分解できる環はデデキント域と呼ばれる。

順序数には一意の因数分解のバージョンがありますが、一意性を保証するためにいくつかの追加条件が必要です。

任意の可換メビウス モノイドは一意の因数分解定理を満たし、したがって正の整数の乗法半群と同様の算術特性を持ちます。算術の基本定理は、実際には、可換メビウス モノイドにおける一意の因数分解定理の特殊なケースです。

• 整数因数分解
• 基本定理と呼ばれる定理の一覧
• 素数シグネチャ、与えられた数を何個の素数が割り切るかを表す特徴

『Disquisitiones Arithmeticae』はラテン語から英語とドイツ語に翻訳されています。ドイツ語版には、数論に関する彼のすべての論文（二次相互法則のすべての証明、ガウス和の符号の決定、双二次相互法則の研究、未発表のメモ）が含まれています。

• ガウス、カール・フリードリヒ（1986）、Disquisitiones Arithemeticae（第2版、訂正版）、クラーク、アーサー・A.訳、ニューヨーク：シュプリンガー、ISBN 978-0-387-96254-2
• Gauss, Carl Friedrich (1965)、Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeteticae & other places on Number Theory) (第 2 版) (ドイツ語)、Maser, H. 訳、ニューヨーク: Chelsea、ISBN 0-8284-0191-8

ガウスが出版した双二次相互性に関する 2 つのモノグラフには、連続番号が付けられたセクションがあります。最初のモノグラフには §§ 1 ～ 23 が含まれ、2 番目のモノグラフには §§ 24 ～ 76 が含まれます。これらを参照する脚注の形式は、「Gauss, BQ, § n」です。Disquisitiones Arithmeticaeを参照する脚注の形式は、「Gauss, DA, Art. n」 です。

• ガウス、カール・フリードリッヒ (1828)、Theoria residuorum biquadraticorum、Commentatio prima、ゲッティンゲン: コメント。社会科学領域、ゲッティンゲン 6
• ガウス、カール・フリードリッヒ (1832)、Theoria residuorum biquadraticorum、Commentatio secunda、ゲッティンゲン: コメント。社会地理領域、ゲッティンゲン 7

これらはガウスの『作品』第2巻、65～92ページと93～148ページに掲載されており、ドイツ語訳は『 Disquisitiones 』ドイツ語版の511～533ページと534～586ページに掲載されています。

• ユークリッド（1956年）『原論』第2巻（第3巻から第9巻）、トーマス・リトル・ヒース訳（第2版完全版）、ニューヨーク：ドーバー、ISBN 978-0-486-60089-5
• ハーディ、GH ;ライト、EM (2008) [1938]、数論入門、 DRヒースブラウンとJHシルバーマン改訂。アンドリュー・ワイルズによる序文。(第6版)、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-921986-5、MR  2445243、Zbl  1159.11001
• ロング、カルビン T. (1972)、初等数論入門(第 2 版)、レキシントン: DC ヒース アンド カンパニー、LCCN  77-171950。
• ペットフレッツォ、アンソニー J.; バーキット、ドナルド R. (1970)、数論の要素、イングルウッド クリフス:プレンティス ホール、LCCN  77-81766。
• リーゼル、ハンス（1994）、素数と因数分解のためのコンピュータ手法（第2版）、ボストン：ビルクハウザー、ISBN 0-8176-3743-5
• ヴェイユ、アンドレ (2007) [1984]、「数論：ハンムラピからルジャンドルまでの歴史を通したアプローチ」、モダン・ビルクハウザー・クラシックス、ボストン、マサチューセッツ州：ビルクハウザー、ISBN 978-0-817-64565-6

• 算術の基本定理がなぜ明白ではないのでしょうか?
• GCD とcut-the-knotにおける算術の基本定理。
• PlanetMath: 算術の基本定理の証明
• フェルマーの最終定理ブログ: Unique Factorization は、アレクサンドリアのディオファントスからアンドリュー・ワイルズによる証明までのフェルマーの最終定理の歴史を解説したブログです。
• 「算術の基本定理」Hector Zenil 著、Wolfram Demonstrations Project、2007 年。
• グライム、ジェームズ（2012年2月3日）、「1と素数」、Numberphile、ブレイディ・ハラン、2021年12月11日時点のオリジナルよりアーカイブ