コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

ユークリッドの補題

出典: フリー百科事典『ウィキペディア(Wikipedia)』

ユークリッドの補題(ユークリッドのほだい、: Euclid's lemma)またはユークリッドの第一定理(ユークリッドのだいいちていり、: Euclid's first theorem)とは素数に関する基本的な性質について述べた次の補題である:

ユークリッドの補題 ― 素数 p が 2 つの整数の ab割り切るなら、その素数 pa または b の少なくとも 1 つを割り切る。

この性質は整数論の基本定理を証明する鍵となる[注釈 1] [注釈 2]

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

[編集]

たとえば、p = 19a = 133b = 143 の場合、ab = 133 × 143 = 19019 について、ab = 19019p = 19 で割り切れるので、ユークリッドの補題から a = 133, b = 143 の少なくとも一方は p = 19 で割り切ることができる。実際、133 ÷ 19 = 7 であり a = 133p = 19 で割り切れる。

反例

[編集]

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

定式化

[編集]

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

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

  • p a かつ p b ならば p ab
  • p a かつ p ab ならば p b

一般化

[編集]

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

定理 ― ca互いに素であり、かつ c ab ならば、c b である。

この定理がユークリッドの補題の一般化であることは、c が素数なら

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

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

証明

[編集]

ベズーの補題による証明

[編集]

ベズーの補題を利用した証明をする[1]。ベズーの補題によれば、x, y互いに素な整数であるなら(x, y最大公約数1 であるなら)、

(1)

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

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

(2)

(2) の両辺に b を掛ければ

(3)

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

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

[編集]

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

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

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

の関係がある。…③

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

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

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

『原論』の証明

[編集]

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

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

脚注

[編集]

注釈

[編集]
  1. ^ 一般に、一意分解整域であることを示すことは、ユークリッドの補題と主イデアルの昇鎖条件英語版 (ACCP) を導くには充分である。
  2. ^ 一般の代数学において「積を割り切るならば何れか一つの因子を割り切る」という性質は素元、すなわち任意の可換環における一般化された素数の定義に用いられる。一方、素数の定義「自分自身と単数以外に因子を持たない」を満たすものは既約元という。そのうえで、任意の可換環(特に整域R において「任意の既約元は素元である(したがって素元と既約元は同値な概念となる)」という主張を一般に「ユークリッドの補題」と呼ぶ。この場合、R によってユークリッドの補題は真にも偽にもなり得る。真となる整域 REL 整域 (Euclid's Lemma domain) と呼ぶ。
  3. ^ すなわち,abcd ならば adbc およびその逆[3]
  4. ^ すなわち,abcd で,a, b がこの関係を満足するうちの最小の数とすれば,自然数 n≧1 があって,cna, dnb となる[4]
  5. ^ すなわち,abcd で,a, b が互いに素とすれば,a, b がこの関係を満足するうちの最小の数となる[5]
  6. ^ 素数はそれの倍数以外のすべての数に対して素である[6]
  7. ^ 素数 cab を割り切るならば,ca または b を割り切る[7]

出典

[編集]

参考文献

[編集]
  • Hardy, G. H.; Wright, E. M.; Wiles, A. J. (2008-09-15), An Introduction to the Theory of Numbers (6th ed.), Oxford: Oxford University Press, ISBN 978-0-19-921986-5 
    • G. H・ハーディ、E. M・ライト『数論入門 I』丸善出版、2012年1月。ISBN 978-4-621-06226-5  - 原書第5版(1979年刊)の邦訳。
  • ハイベア・メンゲ 編『ユークリッド原論』中村幸四郎寺阪英孝伊東俊太郎池田美恵訳・解説、共立出版  - 全13巻の最初の邦訳。
  • ハイベア・メンゲ 編『エウクレイデス全集』 (全5巻)、東京大学出版会  - 「エウクレイデス全集」の世界初の近代語訳。
  • Euclid (1956). The Thirteen Books of the Elements. Vol. 2 (Books III-IX). トーマス・L・ヒース英語版. Dover Publications. ISBN 978-0-486-60089-5 - vol. 2
  • 高木貞治『初等整数論講義』(第2版)共立出版、1971年10月。ISBN 978-4-320-01001-7 

関連項目

[編集]

外部リンク

[編集]