ユークリッドの補題

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

この性質は整数論の基本定理を証明する鍵となる一般に、域が一意分解整域であることを示すことは、ユークリッドの補題と (ACCP) を導くには充分である。。

ユークリッドの補題の名は、古代ギリシアの数学者アレクサンドリアのエウクレイデスの著作『原論』第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

ユークリッドの補題

Źródło i licencja