ユークリッドの補題
ユークリッドの補題（ユークリッドのほだい、英: Euclid's lemma）またはユークリッドの第一定理（ユークリッドのだいいちていり、英: Euclid's first theorem）とは素数に関する次の基本的な性質について述べた補題である： テンプレート:Math theorem たとえば、p = 19、a = 133、b = 143 の場合、ab = 133 × 143 = 19019 について、ab = 19019 は p = 19 で割り切れるので、ユークリッドの補題から a = 133, b = 143 の少なくとも一方は p = 19 で割り切ることができる。実際、133 ÷ 19 = 7 であり a = 133 は p = 19 で割り切れる。
この性質は整数論の基本定理を証明する鍵となる[注釈 1]。これは素元、すなわち任意の可換環における一般化された素数の定義に用いられる。
ユークリッドの補題は合成数に対しては成り立たない。 たとえば、p = 10、a = 4、b = 15 の場合、合成数 p = 10 は積 ab = 4 × 15 = 60 を割り切るにもかかわらず、 p = 10 は a = 4 を割り切れないし b = 15 も割り切ることができない (ab = 60 = 10 × 6)。
ユークリッドの補題の名は、古代ギリシアの数学者アレクサンドリアのエウクレイデスの著作『原論』第7巻の命題30で示されたことによる。
Contents
定式化
p を素数とし、2 つの整数 a, b の積 ab は p で割り切れるとする（このことは記号的に p|ab と表す。これの否定は płab と表され、ab が p で割り切れないことを示す）。このとき 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
- c は a と互いに素のため 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]。
- 証明
- 素数 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 を割り切る。
これが証明すべきことであった[7]。
脚注
注釈
- ↑ 一般に、域が一意分解整域であることを示すことは、ユークリッドの補題と主イデアルの昇鎖条件 (ACCP) を導くには充分である。
- ↑ すなわち，a ： b＝c ： d ならば ad＝bc およびその逆[2]。
- ↑ すなわち，a ： b＝c ： d で，a, b がこの関係を満足するうちの最小の数とすれば，自然数 n≧1 があって，c＝na, d＝nb となる[3]。
- ↑ すなわち，a ： b＝c ： d で，a, b が互いに素とすれば，a, b がこの関係を満足するうちの最小の数となる[4]。
- ↑ 素数はそれの倍数以外のすべての数に対して素である[5]。
- ↑ 素数 c が ab を割り切るならば，c は a または b を割り切る[6]。
出典
- ↑ {{#invoke:Footnotes | harvard_citation }}
- ↑ {{#invoke:Footnotes | harvard_citation }}
- ↑ {{#invoke:Footnotes | harvard_citation }}
- ↑ {{#invoke:Footnotes | harvard_citation }}
- ↑ {{#invoke:Footnotes | harvard_citation }}
- ↑ {{#invoke:Footnotes | harvard_citation }}
- ↑ {{#invoke:Footnotes | harvard_citation }}
参考文献
- 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-01。ISBN 978-4-621-06226-5。 - 原書第5版（1979年刊）の邦訳。
- 『ユークリッド原論』 ハイベア・メンゲ編、中村幸四郎・寺阪英孝・伊東俊太郎・池田美恵訳・解説、共立出版。 - 全13巻の最初の邦訳。
- 『エウクレイデス全集』（全5巻）、ハイベア・メンゲ編、東京大学出版会。 - 「エウクレイデス全集」の世界初の近代語訳。
- Euclid (1956). The Thirteen Books of the Elements, トーマス・L・ヒース, Dover Publications. ISBN 978-0-486-60089-5. - vol. 2
関連項目
外部リンク
- Weisstein, Eric W. “Euclid's Lemma”. MathWorld（英語）. Template:Cite webの呼び出しエラー：引数 accessdate は必須です。