算術の基本定理（ユニークな因数分解の定理ともいう）は、数論の定理である。この定理は、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 より大きい任意の整数は素数の積として表せ、表し方は（順序を除いて）ただ一つである」という非常に基本的かつ強力な事実です。証明には帰納法とユークリッドの補題が用いられ、数論・代数・暗号理論など多くの分野で根本的役割を果たします。