ユークリッドの補題

提供: testwiki
ナビゲーションに移動 検索に移動

ユークリッドの補題（ユークリッドのほだい、テンプレート:Lang-en-short）またはユークリッドの第一定理（ユークリッドのだいいちていり、テンプレート:Lang-en-short）とは素数に関する基本的な性質について述べた次の補題である： テンプレート:Math theorem この性質は整数論の基本定理を証明する鍵となる[注釈 1] テンプレート:Efn。

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

例

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

反例

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

定式化

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

p∣ab⇒p∣a∨p∣b(p∤ab∨p∣a∨p∣b).

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

p∤a∧p∤b⇒p∤ab
p∤a∧p∣ab⇒p∣b

一般化

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

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

証明

ベズーの補題による証明

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

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

最小公倍数・最大公約数の性質から

公倍数は最小公倍数の倍数である。…①

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

二つの正整数 a,c の最小公倍数を l、最大公約数を g とするとき、

ac=lg

の関係がある。…③

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

今 a,c が互いに素であるとき g=1．ゆえに l=lcm(a,c)=ac．…④

ここでユークリッドの補題の前提条件として a,c が互いに素であり、かつ c∣ab のとき， ab は c の倍数かつ、当然 a の倍数であるから、ab は a,c の公倍数． ④より lcm(a,c)=ac で①より ac∣ab．ゆえに c∣b. これが証明すべきことであった．[2]

『原論』の証明

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

テンプレート:Anchors命題19
もし四つの数が比例するならば，第1と第4の積は第2と第3の積に等しいであろう。そしてもし第1と第4の積が第2と第3の積に等しいならば，四つの数は比例するであろうテンプレート:Refnest。
テンプレート:Anchors命題20
同じ比をもつ2数のうち最小の数はそれと同じ比をもつ2数を，大きい数が大きい数を，小さい数が小さい数をそれぞれ割り切り，その商は等しいテンプレート:Refnest。
テンプレート:Anchors命題21
互いに素である2数はそれらと同じ比をもつ2数のうち最小であるテンプレート:Refnest。
テンプレート:Anchors命題29
すべて素数はそれが割り切らないすべての数に対して素であるテンプレート:Refnest。
テンプレート:Anchors命題30
もし二つの数が互いにかけあわせてある数をつくり，2数の積を何らかの素数が割り切るならば，それは最初の2数の一つを割り切るであろうテンプレート:Refnest。
証明
素数 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 を割り切る。
これが証明すべきことであった[3]。

脚注

テンプレート:脚注ヘルプ

注釈

テンプレート:Reflist

出典

テンプレート:Reflist

参考文献

関連項目

テンプレート:Div col

テンプレート:Div col end

外部リンク


引用エラー: 「注釈」という名前のグループの <ref> タグがありますが、対応する <references group="注釈"/> タグが見つかりません

  1. ↑ テンプレート:Harv
  2. ↑ テンプレート:Harv
  3. ↑ テンプレート:Harv
「https://ja.wiki.beta.math.wmflabs.org/w/index.php?title=ユークリッドの補題&oldid=9595」から取得