ユークリッドの補題

ユークリッドの補題（ユークリッドのほだい、）またはユークリッドの第一定理（ユークリッドのだいいちていり、）とは素数に関する基本的な性質について述べた次の補題である：

この性質は整数論の基本定理を証明する鍵となる
。

ユークリッドの補題の名は、古代ギリシアの数学者アレクサンドリアのエウクレイデスの著作『原論』第7巻の命題30で示されたことによる。

例 
たとえば、、、 の場合、 について、 は  で割り切れるので、ユークリッドの補題から ,  の少なくとも一方は  で割り切ることができる。実際、 であり  は  で割り切れる。

反例 
ユークリッドの補題は  が合成数の場合には成り立たない。
たとえば、、、 の場合、合成数  は積  を割り切るにもかかわらず、  は  を割り切れないし  も割り切ることができない ()。

定式化 
 を素数とし、2 つの整数  の積  は  で割り切れるとする（このことは記号的に  と表す。これの否定は  と表され、 が  で割り切れないことを示す）。このとき  または 、あるいはその両方が成り立つ。

同値な言明として以下のようなものがある。
 かつ  ならば 

  かつ  ならば

一般化 
一般化された補題もまたユークリッドの補題と呼ばれる：

この定理がユークリッドの補題の一般化であることは、 が素数なら
 
  は  と互いに素のため 、従って 
のいずれかであることによる。

証明

ベズーの補題による証明 
ベズーの補題を利用した証明をする。ベズーの補題によれば、 が互いに素な整数であるなら（ の最大公約数が  であるなら）、

を満たすような整数  が存在する。

 が互いに素であり、かつ  であるとすれば、ベズーの等式  より、以下の等式を得る。

 の両辺に  を掛ければ

となる。 の左辺の第一項は  で割り切れ、第二項は  で割り切れるので仮定より  でも割り切れる。従ってそれらの和も  で割り切れるから  が成り立つ。これは上述のユークリッドの補題の一般化になっている。

最小公倍数・最大公約数の性質から 
公倍数は最小公倍数の倍数である。…①

公約数は最大公約数の約数である。…②

二つの正整数  の最小公倍数を 、最大公約数を  とするとき、

の関係がある。…③

③は①②より直接証明できる。

今  が互いに素であるとき ．ゆえに ．…④

ここでユークリッドの補題の前提条件として  が互いに素であり、かつ  のとき，
 は  の倍数かつ、当然  の倍数であるから、 は  の公倍数．
④より  で①より ．ゆえに . これが証明すべきことであった．

『原論』の証明 
『原論』では第7巻の命題30において、ユークリッドの補題が証明されている。『原論』にある証明はそのままでは意味を理解することが難しいので、にある証明を引用する。

命題19
もし四つの数が比例するならば，第1と第4の積は第2と第3の積に等しいであろう。そしてもし第1と第4の積が第2と第3の積に等しいならば，四つの数は比例するであろう。
命題20
同じ比をもつ2数のうち最小の数はそれと同じ比をもつ2数を，大きい数が大きい数を，小さい数が小さい数をそれぞれ割り切り，その商は等しい。
命題21
互いに素である2数はそれらと同じ比をもつ2数のうち最小である。
命題29
すべて素数はそれが割り切らないすべての数に対して素である。
命題30
もし二つの数が互いにかけあわせてある数をつくり，2数の積を何らかの素数が割り切るならば，それは最初の2数の一つを割り切るであろう。
証明
素数 c が ab を割り切るならば，c は a または b を割り切るであろう。c が a を割り切らないと仮定せよ。そうすれば，［命題29］より，c と a は互いに素である。ab＝mc と仮定せよ。そうすれば，［命題19］より，c ： a＝b ： m となる。そうすれば，［命題20］と［命題21］より，自然数 n≧1 があって，b＝nc となる。したがって，c は b を割り切る。同様にして，c が b を割り切らないとき，c は a を割り切る。したがって，c は a または b を割り切る。これが証明すべきことであった。

脚注

注釈

出典

参考文献 

 - 原書第5版（1979年刊）の邦訳。
 - 全13巻の最初の邦訳。

（抜粋）『世界の名著9』 池田美恵訳 中央公論社 1972年。

 - 「エウクレイデス全集」の世界初の近代語訳。
 第2巻  原論VII－X、斎藤憲 訳・解説、2015年8月。ISBN 978-4-13-065302-2
- vol. 2

関連項目 

整数論の基本定理
ベズーの等式
ユークリッドの互除法
有理根定理

外部リンク 

ユークリッドの補題の証明

エウクレイデス
算術
数学に関する記事
数論