算術の基本定理とは一意的因数分解の定義・証明・暗号応用
算術の基本定理（ユニークな因数分解の定理ともいう）は、数論の定理である。この定理は、1より大きいすべての正の整数は、素数の積として書くことができる（または、その整数自体が素数である）というもので、さらにその表し方は順序を除いて一意である、というものです。もし二人の人が同じ整数について異なる素因数分解を見つけたとしたら、異なっているのは単に素数の並べ方（順序）のみで、それ以外の違いは起こりません。
例：6936 = 23×3×172 または 1200 = 24×3×52
ある整数を素数の積として表す操作を因数分解と呼びます。1 は特別で「単位」と呼ばれ、素数でも合成数でもないため、上の定理は「1より大きい整数」について述べられます。
定理の正確な定式化
算術の基本定理（正式）：任意の整数 n > 1 に対して、n は有限個の素数の積として表せる（存在性）。また、そのような表現は素数の順序を除いて一意である（一意性）。
証明の概略
- 存在性（強い帰納法を用いる）
n が素数であれば成り立ちます。合成数であれば n = a b となる a,b は n より小さい正整数なので、帰納法の仮定により a,b は素数の積として書けます。したがって n も素数の積として書けます。 - 一意性（ユークリッドの補題を用いる）
ユークリッドの補題：素数 p が ab に割り切れるなら、p は a または b の少なくとも一方に割り切れる。
一意性はこの補題を繰り返し適用して示します。もし n の二つの素因数分解 p1·p2·…·pr と q1·q2·…·qs（それぞれ素数）とし、p1 が q1,…,qs のいずれかに等しくないと仮定すると、p1 は右辺の積を割り切るので補題によりいずれかの qi を割るはずです。qi が素数なので qi = p1 であり、これを取り除いて同様の議論を繰り返すと、最終的に素因数の集合（重複を含めた数え方）が一致することが示せます。 - ユークリッドの補題自体は、最大公約数やベズーの等式（整係数の一次結合で 1 を表せること）を使って示せます。
具体例と注意点
- 上の例 6936 = 23×3×172 は一意的で、仮に別の分解があっても素数の集合（重複を含む）は同じになります（順序を除く）。
- 「一意」とは厳密には「順序を除いて一意」であり、素因数の並び替えは異なる表記に過ぎません。
- 1 は因数分解の対象外（単位）で、1 の素因数分解は定義しません。
応用
- この定理は基本的な算術の性質の土台であり、最大公約数・最小公倍数や算術関数（例えば約数の個数関数、トーシェント関数など）の理論で重要です。
- 暗号分野でも重要です。公開鍵暗号方式の代表であるRSAは、大きな合成数（特に二つの大きな素数の積）を因数分解することが計算上難しいことに安全性を依存しています。因数分解アルゴリズム（試し割り、楕円曲線法、二次篩、一般数体篩（GNFS）など）の改良は暗号の安全性に直接影響します（参考：暗号）。
- 代数的な一般化として、整域における一意分解整域（UFD: unique factorization domain）の概念があり、算術の基本定理は整数環 Z が UFD であることの表現です。
まとめ
算術の基本定理は「1 より大きい任意の整数は素数の積として表せ、表し方は（順序を除いて）ただ一つである」という非常に基本的かつ強力な事実です。証明には帰納法とユークリッドの補題が用いられ、数論・代数・暗号理論など多くの分野で根本的役割を果たします。
証明
この定理を最初に証明したのはユークリッドである。最初の詳細で正しい証明は、カール・フリードリヒ・ガウスの Disquisitiones Arithmeticae に記載されている。
この定理はどこでも成り立つと思っている人がいるかもしれません。しかし、この定理は、代数的整数のような、より一般的な数の体系では成り立ちません。このことは、1843年にErnst KummerがFermatの最終定理に関する研究で初めて言及しました。それについての詳細は：代数的整数論をお読みください。
この証明は2つの部分から構成されています。まず、すべての数は素数の積として書くことができることを示し、次に、ある数を2回目に素数の積として書いた場合、素数の2つのリストは同じでなければならないことを示します。
証明の最初の部分
私たちは、1より大きいすべての数が素数の積として書けなければ、ある種の不可能性に行き着くことを示しました。その結果、すべての数が素数の積として書けることは真実でなければならないという結論に達しました。
では、誰かが「素数の積として書けない1以上の正の整数を知っている」と言ったらどうなるでしょうか。この場合、私たちはその人に、素数の積として書けない1以上の数をすべて挙げてもらいます。その中で一番小さい数をnとします。もちろん、このnは1ではありません。なぜなら、素数は1つの素数、つまり自分自身の「積」であるからです。つまり、数の積でなければなりません。したがって
n = ab
ここで，aとbはともに正の整数で，もちろんnよりも小さい。しかし，nは素数の積として書けない最小の数である。ということは、aとbはどちらもnより小さいので、素数の積として書くことができるはずです。
n = ab
は、素数の積としても書くことができます。これは、nを素数の積として書くことはできないと言ったので、不可能なことです。
これで、定理の最初の部分が成立しない場合に存在する不可能性を示しました。このようにして、私たちは定理の最初の部分を証明しました。
証明の第二部
今度は、1より大きい正の数を素数の積として書く方法が1つしかないことを証明しなければなりません。
そのためには、次のようなレンマを利用します。素数pが積abを分割する場合、aを分割するかbを分割するか、というものです（ユークリッドのレンマ）。まず、このレンマを証明します。さて、pがaを割らないと仮定します。そうすると、pとaは共起であり、次のような整数xとyが存在しなければならないというベゾウトの恒等式が成り立ちます。
px + ay = 1となります。
すべてにbをかけると
pbx + aby = bです。
つまり、左辺にはpで割り切れる2つの項があり、右辺の項もpで割り切れることになります。これで、pがaを割り切れないなら、bを割り切れるはずだということが証明されました。
ここでは、1より大きい整数を素数の積として1通りしか書けないことを証明します。結果が同じになる素数AとBの2つの積を考えます。最初の積Aから任意の素数pを取ります。それはAを割るので、Bも割ることになります。先ほど証明したレンマを何度か使うと、pはBの少なくとも1つの因子bを割らなければならないことがわかります。しかし、因子はすべて素数なので、bも素数です。そこで、Aをpで割り、Bもpで割ってみると、A* = B*のような結果が得られます。この場合も、最初の積A*から素数pを取り出し、それが積B*のある数に等しいことがわかります。このようにして続けていくと、最後には2つの積の素因数が全く同じでなければならないことがわかります。これは、正の整数を素数の積として書くことができる唯一の方法であることを証明しています。
質問と回答
Q:算術の基本定理とは何ですか?
A:算術の基本定理とは、1より大きい正の整数はすべて素数の積として書くことができ、その書き方は1通りしかないという数論の定理です。
Q:この定理はどのように使えるのですか?
A:この定理は暗号に使うことができます。
Q:2人が同じ数の書き方を2種類見つけるとどうなるか?
A:二人が同じ数の書き方を二通り見つけた場合、異なるのは素数の書き順だけである。
Q:因数分解とは何ですか?
A:因数分解とは、与えられた数を構成するすべての素数を見つけることです。
Q:6936は素数の一例ですか?
A:いいえ、6936は素数ではありません、23 - 3 - 172と書くことができます。
いいえ、6936は素数ではありません、23 - 3 - 172と書くことができます。
