ユークリッドの補題

提供: miniwiki
移動先:案内検索

ユークリッドの補題(ユークリッドのほだい、: Euclid's lemma)またはユークリッドの第一定理(ユークリッドのだいいちていり、: Euclid's first theorem)とは素数に関する次の基本的な性質について述べた補題である: テンプレート:Math theorem たとえば、p = 19a = 133b = 143 の場合、ab = 133 × 143 = 19019 について、ab = 19019p = 19 で割り切れるので、ユークリッドの補題から a = 133, b = 143 の少なくとも一方は p = 19 で割り切ることができる。実際、133 ÷ 19 = 7 であり a = 133p = 19 で割り切れる。

この性質は整数論の基本定理を証明する鍵となる[注釈 1]。これは素元、すなわち任意の可換環における一般化された素数の定義に用いられる。

ユークリッドの補題は合成数に対しては成り立たない。 たとえば、p = 10a = 4b = 15 の場合、合成数 p = 10 は積 ab = 4 × 15 = 60 を割り切るにもかかわらず、 p = 10a = 4 を割り切れないし b = 15 も割り切ることができない (ab = 60 = 10 × 6)。

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

定式化

p素数とし、2 つの整数 a, b の積 abp で割り切れるとする(このことは記号的に p|ab と表す。これの否定は płab と表され、abp で割り切れないことを示す)。このとき p|a または p|b、あるいはその両方が成り立つ。

[math]p \mid ab \Rightarrow p \mid a \lor p \mid b \qquad \left(p \nmid ab \lor p \mid a \lor p \mid b \right).[/math]

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

  • pła かつ płb ならば płab
[math]p \nmid a \land p \nmid b \Rightarrow p \nmid ab[/math]
  • pła かつ p|ab ならば p|b
[math]p \nmid a \land p \mid ab \Rightarrow p \mid b[/math]

一般化された補題もまたユークリッドの補題と呼ばれる: テンプレート:Math theorem この定理がユークリッドの補題の一般化であることは、c が素数なら

  • c|a
  • ca と互いに素のため cła、従って c|b

のいずれかであることによる。

証明

ベズーの補題による証明

ベズーの補題を利用した証明をする[1]。ベズーの補題によれば、x, y互いに素な整数であるなら(x, y最大公約数1 であるなら)、 テンプレート:NumBlk を満たすような整数 r, s が存在する。

a, c が互いに素であり、かつ c|ab であるとすれば、ベズーの等式 テンプレート:EquationNote より、以下の等式を得る。 テンプレート:NumBlk テンプレート:EquationNote の両辺に b を掛ければ テンプレート:NumBlk となる。テンプレート:EquationNote の左辺の第一項は c で割り切れ、第二項は ab で割り切れるので仮定より c でも割り切れる。従ってそれらの和も c で割り切れるから c|b が成り立つ。これは上述のユークリッドの補題の拡張になっている。

『原論』の証明

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

命題19
もし四つの数が比例するならば,第1と第4の積は第2と第3の積に等しいであろう。そしてもし第1と第4の積が第2と第3の積に等しいならば,四つの数は比例するであろう[注釈 2]
命題20
同じ比をもつ2数のうち最小の数はそれと同じ比をもつ2数を,大きい数が大きい数を,小さい数が小さい数をそれぞれ割り切り,その商は等しい[注釈 3]
命題21
互いに素である2数はそれらと同じ比をもつ2数のうち最小である[注釈 4]
命題29
すべて素数はそれが割り切らないすべての数に対して素である[注釈 5]
命題30
もし二つの数が互いにかけあわせてある数をつくり,2数の積を何らかの素数が割り切るならば,それは最初の2数の一つを割り切るであろう[注釈 6]
証明
素数 cab を割り切るならば,ca または b を割り切るであろう。
ca を割り切らないと仮定せよ。
そうすれば,[命題29]より,ca は互いに素である。
abmc と仮定せよ。
そうすれば,[命題19]より,cabm となる。
そうすれば,[命題20]と[命題21]より,自然数 n≧1 があって,bnc となる。
したがって,cb を割り切る。
同様にして,cb を割り切らないとき,ca を割り切る。
したがって,ca または b を割り切る。
これが証明すべきことであった[7]

脚注

注釈

  1. 一般に、一意分解整域であることを示すことは、ユークリッドの補題と主イデアルの昇鎖条件English版 (ACCP) を導くには充分である。
  2. すなわち,abcd ならば adbc およびその逆[2]
  3. すなわち,abcd で,a, b がこの関係を満足するうちの最小の数とすれば,自然数 n≧1 があって,cna, dnb となる[3]
  4. すなわち,abcd で,a, b が互いに素とすれば,a, b がこの関係を満足するうちの最小の数となる[4]
  5. 素数はそれの倍数以外のすべての数に対して素である[5]
  6. 素数 cab を割り切るならば,ca または b を割り切る[6]

出典

  1. {{#invoke:Footnotes | harvard_citation }}
  2. {{#invoke:Footnotes | harvard_citation }}
  3. {{#invoke:Footnotes | harvard_citation }}
  4. {{#invoke:Footnotes | harvard_citation }}
  5. {{#invoke:Footnotes | harvard_citation }}
  6. {{#invoke:Footnotes | harvard_citation }}
  7. {{#invoke:Footnotes | harvard_citation }}

参考文献

関連項目

外部リンク