ユークリッドの補題：素数による積の整除性

命題と同値な形

この補題は通常、二つの同値な形で表される。素数が積を割り切る性質、すなわち p が素数で p|ab ならば p|a または p|b、という形と、互いに素を用いる形、すなわち p|ab かつ gcd(p,a)=1 ならば p|b、という形である。文脈に応じて両方の定式化が使われる。これは、整数 a と b>0 に対して、一意な q と r が存在し、a=bq+r および 0≤r<b となるとする「除法補題」または除法算法とは別のものである。

証明の概略

短い古典的な証明では、最大公約数の性質を用いる。p が ab を割り切るが a を割り切らないとすると、gcd(a,p)=1 である。ベズーの等式により、整数 x、y が存在して ax+py=1 となる。これに b を掛けると、abx+pby=b を得る。p は abx を割り切り、また pby も割り切るので、右辺の b も割り切る。したがって p|b である。この初等的な議論は、より深い因数分解に関する事実を用いない。

例と対比

• 例：p=3 は 3・20=60 を割り切り、実際に 3 は 3 を割り切る（または 3 を含む任意の因数を割り切る）。
• 対比：この性質は合成数の除数については成り立たない。たとえば 6 は 2・3 を割り切るが、6 は 2 も 3 も割り切らない。

歴史、重要性と用途

この結果はユークリッドに帰され、『原論』第VII巻に現れ、整除と素数に関する議論で役割を果たしている。現代の解説ではユークリッドの補題、またはユークリッドの第一定理と呼ばれる。歴史的な論考や版については、多くの数論入門書、ならびにユークリッドに関する資料や補題に関する資料などの古典資料で扱われている。この補題は算術の基本定理（整数の一意因数分解）の通常の証明における中心的要素であり、たとえば素数が無限に存在することや有理数の性質を示す際に用いられる。

一般化と関連概念

ユークリッドの補題に類する性質は抽象代数学にも現れる。整域では、積を割り切るならば一方の因子を割り切る元 p を素元と呼ぶ。一意分解整域（UFD）では素元と既約元は一致し、ユークリッドの補題の一形態が成り立つ。関連する補題や形式的定義の背景については、標準的な文献および補題についての資料、数論の基礎についての資料を参照されたい。