可除性と素数

可除性、最大公約数、および素数は、数論の基礎を形成します。すべての整数は素数から乗法的に構成され、その構成方法がその後のほぼすべての結果を支配します。

Definition

整数 a が b を割り切るとは、b が a にある整数を掛けたものに等しい場合を指します。素数とは、1 より大きい整数で、その正の約数が 1 とそれ自身のみであるものです。可除性と素数は、整数の乗法的な分解と、その分解の既約な構成要素に関係します。

Scope

このトピックでは、整数の可除性関係、除法のアルゴリズム、ユークリッドの互除法によって計算される最大公約数と最小公倍数、ベズーの等式、ユークリッドの補題、算術の基本定理、および素数の初等理論（その無限性、分布のヒューリスティクス、素数性）を扱います。

Core questions

• ユークリッドの互除法はどのように最大公約数を計算し、ベズーの等式を導き出すのでしょうか？
• ユークリッドの補題はなぜ素数への因数分解が一意であることを強制するのでしょうか？
• 素数が無限に存在することをどのように証明できるのでしょうか、そしてそのような証明は何を明らかにするのでしょうか？
• 素数は整数の中にどのように分布しており、素数性は実際にどのように決定されるのでしょうか？

Key theories

除法のアルゴリズムとユークリッドの互除法

任意の整数を正の整数で割ると、一意の商と余りが残ります。これを繰り返すことで最大公約数が得られ、逆代入によって、それを線形結合（ベズーの等式）として表現する整数が得られます。

算術の基本定理

1より大きいすべての整数は、順序を除いて一意な素数の積です。ユークリッドの補題（積を割り切る素数はその因数を割り切る）が重要なステップです。

素数の無限性

ユークリッドの古典的な議論は、素数の有限なリストが完全ではないことを示しています。ゼータ関数のオイラー積公式は解析的な証明を与え、素数の逆数の和の発散を通じて素数の密度を定量化します。

Clinical relevance

高速な因数分解と素数判定は、暗号学の基礎です。RSAのセキュリティは、2つの素数の大きな積を因数分解することの困難性に基づいており、効率的な素数判定法（ミラー-ラビンなど）は鍵生成を実用的なものにしています。

History

ユークリッドの『原論』（紀元前300年頃）には、すでにユークリッドの互除法、ユークリッドの補題、および素数が無限に存在するという証明が含まれていました。エラトステネスの篩は、素数を列挙する最初の系統的な方法を提供し、18世紀から19世紀にかけてのオイラー、ルジャンドル、ガウスによる研究は、素数の分布を定量的な問題として再構築しました。

Key figures

• Euclid
• Eratosthenes
• Leonhard Euler
• Etienne Bezout

Seminal works

• hardyWright2008

Frequently asked questions

1は素数ですか？

いいえ。素因数分解が一意であるように、1は定義から除外されています。もし1が素数と数えられた場合、すべての数は無限に多くの因数分解を持つことになります。

ベズーの等式は何に使われますか？

これは、2つの整数の最大公約数がそれらの整数の線形結合であることを示しており、モジュラー逆数を計算したり、線形ディオファントス方程式を解いたりするための基礎となります。