ユークリッドの補題

ユークリッドの補題（ユークリッドのほだい、）またはユークリッドの第一定理（ユークリッドのだいいちていり、）とは素数に関する基本的な性質について述べた次の補題である：
この性質は整数論の基本定理を証明する鍵となる
ユークリッドの補題の名は、古代ギリシアの数学者アレクサンドリアのエウクレイデスの著作『原論』第7巻の命題30で示されたことによる。
例.
たとえば、、、 の場合、 について、 は で割り切れるので、ユークリッドの補題から , の少なくとも一方は で割り切ることができる。実際、 であり は で割り切れる。
反例.
ユークリッドの補題は が合成数の場合には成り立たない。
たとえば、、、 の場合、合成数 は積 を割り切るにもかかわらず、 は を割り切れないし も割り切ることができない ()。
定式化.
 を素数とし、2 つの整数 の積 は で割り切れるとする（このことは記号的に と表す。これの否定は と表され、 が で割り切れないことを示す）。このとき または 、あるいはその両方が成り立つ。
同値な言明として以下のようなものがある。
一般化.
一般化された補題もまたユークリッドの補題と呼ばれる：
この定理がユークリッドの補題の一般化であることは、 が素数なら
のいずれかであることによる。
証明.
ベズーの補題による証明.
ベズーの補題を利用した証明をする。ベズーの補題によれば、 が互いに素な整数であるなら（ の最大公約数が であるなら）、
を満たすような整数 が存在する。
 が互いに素であり、かつ であるとすれば、ベズーの等式 より、以下の等式を得る。
 の両辺に を掛ければ
となる。 の左辺の第一項は で割り切れ、第二項は で割り切れるので仮定より でも割り切れる。従ってそれらの和も で割り切れるから が成り立つ。これは上述のユークリッドの補題の一般化になっている。
最小公倍数・最大公約数の性質から.
公倍数は最小公倍数の倍数である。…①
公約数は最大公約数の約数である。…②
二つの正整数 formula_4 の最小公倍数を formula_5、最大公約数を formula_6 とするとき、
の関係がある。…③
③は①②より直接証明できる。
今 formula_4 が互いに素であるとき formula_9．ゆえに formula_10．…④
ここでユークリッドの補題の前提条件として formula_4 が互いに素であり、かつ formula_12 のとき，
formula_13 は formula_14 の倍数かつ、当然 formula_15 の倍数であるから、formula_13 は formula_4 の公倍数．
④より formula_18 で①より formula_19．ゆえに formula_20. これが証明すべきことであった．
『原論』の証明.
『原論』では第7巻の命題30において、ユークリッドの補題が証明されている。『原論』にある証明はそのままでは意味を理解することが難しいので、にある証明を引用する。