ユークリッドの補題のソースを表示

'''ユークリッドの補題'''（ユークリッドのほだい、{{lang-en-short|Euclid's lemma}}）または'''ユークリッドの第一定理'''（ユークリッドのだいいちていり、{{lang-en-short|Euclid's first theorem}}）とは[[素数]]に関する次の基本的な性質について述べた[[補題]]である：
{{math_theorem|ユークリッドの補題|素数 {{mvar|p}} が 2 つの整数の[[積]] {{mvar|ab}} を[[約数|割り切る]]なら、2 つの整数 {{mvar|a}} または {{mvar|b}} の少なくとも 1 つはその素数 {{mvar|p}} で割り切れる。}}
たとえば、{{math|''p'' {{=}} 19}}、{{math|''a'' {{=}} 133}}、{{math|''b'' {{=}} 143}} の場合、{{math|''ab'' {{=}} 133 &times; 143 {{=}} 19019}} について、{{math|''ab'' {{=}} 19019}} は {{math|''p'' {{=}} 19}} で割り切れるので、ユークリッドの補題から {{math|''a'' {{=}} 133}}, {{math|''b'' {{=}} 143}} の少なくとも一方は {{math|''p'' {{=}} 19}} で割り切ることができる。実際、{{math|133 &divide; 19 {{=}} 7}} であり {{math|''a'' {{=}} 133}} は {{math|''p'' {{=}} 19}} で割り切れる。

この性質は[[算術の基本定理|整数論の基本定理]]を証明する鍵となる<ref group="注釈">一般に、[[非可換整域|域]]が[[一意分解環|一意分解整域]]であることを示すことは、ユークリッドの補題と{{仮リンク|主イデアルの昇鎖条件|en|Ascending chain condition on principal ideals}} (ACCP) を導くには充分である。</ref>。
; 注意: 一般の[[代数学]]において上記「積を割り切るならば何れか一つの因子を割り切る」という性質は[[素元]]、すなわち任意の[[可換環]]における一般化された素数の定義に用いられる。一方、素数の定義「自分自身と単数以外に因子を持たない」を満たすものは[[既約元]]という。そのうえで、任意の可換環（特に整域）{{mvar|R}} において「任意の既約元は素元である（したがって素元と既約元は同値な概念となる）」という主張を一般に「ユークリッドの補題」と呼ぶ{{efn|この場合、{{mvar|R}} によってユークリッドの補題は真にも偽にもなり得る。真となる整域 {{mvar|R}} を '''EL 整域''' ('''E'''uclid's '''L'''emma domain) と呼ぶ。}}。

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

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

== 定式化 ==

{{mvar|p}} を[[素数]]とし、2 つの[[整数]] {{mvar|a, b}} の積 {{mvar|ab}} は {{mvar|p}} で割り切れるとする（このことは記号的に {{math|''p''{{!}}''ab''}} と表す。これの否定は {{math|''p''&#x0142;''ab''}} と表され、{{mvar|ab}} が {{mvar|p}} で割り切れないことを示す）。このとき {{math|''p''{{!}}''a''}} または {{math|''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>

[[同値]]な言明として以下のようなものがある。
*{{math|''p''&#x0142;''a''}} かつ {{math|''p''&#x0142;''b''}} ならば {{math|''p''&#x0142;''ab''}}
::<math>p \nmid a \land p \nmid b \Rightarrow p \nmid ab</math>
* {{math|''p''&#x0142;''a''}} かつ {{math|''p''{{!}}''ab''}} ならば {{math|''p''{{!}}''b''}}
::<math>p \nmid a \land p \mid ab \Rightarrow p \mid b</math>

一般化された補題もまたユークリッドの補題と呼ばれる：
{{math_theorem|''c'' が ''a'' と[[互いに素]]であり、かつ ''c''｜''ab'' ならば、''c''｜''b'' である。}}
この定理がユークリッドの補題の一般化であることは、{{mvar|c}} が素数なら
* {{math|''c''{{!}}''a''}}
* {{mvar|c}} は {{mvar|a}} と互いに素のため {{math|''c''&#x0142;''a''}}、従って {{math|''c''{{!}}''b''}}
のいずれかであることによる。

== 証明 ==
=== ベズーの補題による証明 ===
[[ベズーの補題]]を利用した証明をする<ref>{{Harv|ハーディ|ライト|2012|p=27}}</ref>。ベズーの補題によれば、{{mvar|x, y}} が[[互いに素]]な整数であるなら（{{mvar|x, y}} の[[最大公約数]]が {{math|1}} であるなら）、
{{numBlk|:|<math>rx + sy = 1</math>|{{equationRef|1}}}}
を満たすような整数 {{mvar|r, s}} が存在する。

{{mvar|a, c}} が互いに素であり、かつ {{math|''c''{{!}}''ab''}} であるとすれば、[[ベズーの等式]] {{equationNote|1|(1)}} より、以下の等式を得る。
{{numBlk|:|<math>rc + sa = 1.</math>|{{equationRef|2}}}}
{{EquationNote|2|(2)}} の両辺に {{mvar|b}} を掛ければ
{{numBlk|:|<math>rcb + sab = b</math>|{{equationRef|3}}}}
となる。{{equationNote|3|(3)}} の左辺の第一項は {{mvar|c}} で割り切れ、第二項は {{mvar|ab}} で割り切れるので仮定より {{mvar|c}} でも割り切れる。従ってそれらの和も {{mvar|c}} で割り切れるから {{math|''c''{{!}}''b''}} が成り立つ。これは上述のユークリッドの補題の拡張になっている。

=== 最小公倍数・最大公約数の性質から ===
公倍数は最小公倍数の倍数である。…①

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

二つの正整数 <math>a, c</math> の最小公倍数を <math>l</math>、最大公約数を <math>g</math> とするとき、
:<math>ac = lg</math>
の関係がある。…③

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

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

ここでユークリッドの補題の前提条件として <math>a, c</math> が互いに素であり、かつ <math>c|ab</math> のとき，
<math>ab</math> は <math>c</math> の倍数かつ、当然 <math>a</math> の倍数であるから、<math>ab</math> は <math>a, c</math> の公倍数．
④より <math>lcm(a, c) = ac</math> で①より <math>ac | ab</math>．ゆえに <math>c | b</math>. これが証明すべきことであった．<ref>{{高木|||1971|第1章}}</ref>

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

;{{Anchor|命題19}}
:もし四つの数が比例するならば，第1と第4の積は第2と第3の積に等しいであろう。そしてもし第1と第4の積が第2と第3の積に等しいならば，四つの数は比例するであろう{{refnest|group="注釈"|すなわち，''a'' ： ''b''＝''c'' ： ''d'' ならば ''ad''＝''bc'' およびその逆<ref>{{Harv|ユークリッド|中村ほか|1996|pp=162f}}</ref>。}}。
;{{Anchor|命題20}}
:同じ比をもつ2数のうち最小の数はそれと同じ比をもつ2数を，大きい数が大きい数を，小さい数が小さい数をそれぞれ割り切り，その商は等しい{{refnest|group="注釈"|すなわち，''a'' ： ''b''＝''c'' ： ''d'' で，''a'', ''b'' がこの関係を満足するうちの最小の数とすれば，自然数 ''n''≧1 があって，''c''＝''na'', ''d''＝''nb'' となる<ref>{{Harv|ユークリッド|中村ほか|1996|pp=163f}}</ref>。}}。
;{{Anchor|命題21}}
:互いに素である2数はそれらと同じ比をもつ2数のうち最小である{{refnest|group="注釈"|すなわち，''a'' ： ''b''＝''c'' ： ''d'' で，''a'', ''b'' が互いに素とすれば，''a'', ''b'' がこの関係を満足するうちの最小の数となる<ref>{{Harv|ユークリッド|中村ほか|1996|pp=164f}}</ref>。}}。
;{{Anchor|命題29}}
:すべて素数はそれが割り切らないすべての数に対して素である{{refnest|group="注釈"|素数はそれの倍数以外のすべての数に対して素である<ref>{{Harv|ユークリッド|中村ほか|1996|p=169}}</ref>。}}。
;{{Anchor|命題30}}
:もし二つの数が互いにかけあわせてある数をつくり，2数の積を何らかの素数が割り切るならば，それは最初の2数の一つを割り切るであろう{{refnest|group="注釈"|素数 ''c'' が ''ab'' を割り切るならば，''c'' は ''a'' または ''b'' を割り切る<ref>{{Harv|ユークリッド|中村ほか|1996|pp=169f}}</ref>。}}。
;証明
:素数 ''c'' が ''ab'' を割り切るならば，''c'' は ''a'' または ''b'' を割り切るであろう。<br />''c'' が ''a'' を割り切らないと仮定せよ。<br />そうすれば，［[[#命題29|命題29]]］より，''c'' と ''a'' は互いに素である。<br />''ab''＝''mc'' と仮定せよ。<br />そうすれば，［[[#命題19|命題19]]］より，''c'' ： ''a''＝''b'' ： ''m'' となる。<br />そうすれば，［[[#命題20|命題20]]］と［[[#命題21|命題21]]］より，自然数 ''n''≧1 があって，''b''＝''nc'' となる。<br />したがって，''c'' は ''b'' を割り切る。<br />同様にして，''c'' が ''b'' を割り切らないとき，''c'' は ''a'' を割り切る。<br />したがって，''c'' は ''a'' または ''b'' を割り切る。<br />[[Q.E.D.|これが証明すべきことであった]]<ref>{{Harv|Heath|1956|pp=331f}}</ref>。

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{reflist|group="注釈"}}
=== 出典 ===
{{Reflist|2}}

== 参考文献 ==
*{{citation
  | last1 = Hardy  | first1 = G. H.
  | author1-link = ゴッドフレイ・ハロルド・ハーディ
  | last2 = Wright | first2 = E. M.
  | last3 = Wiles  | first3 = A. J.
  | author3-link = アンドリュー・ワイルズ
  | title = An Introduction to the Theory of Numbers
  | edition = 6th
  | publisher = [[Oxford University Press]]
  | location = Oxford
  | date = 2008-09-15
  | isbn = 978-0-19-921986-5}}
**{{Cite book|和書|author=G. H・ハーディ|coauthors=E. M・ライト|date=2012-01|title=数論入門 I|publisher=丸善出版|isbn=978-4-621-06226-5|url=http://pub.maruzen.co.jp/book_magazine/book_data/search/9784621062265.html|ref={{Harvid|ハーディ|ライト|2012}}}} - 原書第5版（1979年刊）の邦訳。
*{{Cite book|和書|editor=[[ヨハン・ルードウィッヒ・ハイベア|ハイベア]]・[[ハインリッヒ・メンゲ|メンゲ]]編|others=[[中村幸四郎]]・[[寺阪英孝]]・[[伊東俊太郎]]・[[池田美恵]]訳・解説|title=ユークリッド原論|publisher=[[共立出版]]|ref={{Harvid|ユークリッド|中村ほか|1971}}}} - 全13巻の最初の邦訳。
**{{Cite book|和書|date=1971-07|title=ユークリッド原論|edition=ハードカバー|isbn=978-4-320-01072-7|ref={{Harvid|ユークリッド|中村ほか|1971}}}}
***（抜粋）『[[世界の名著]]9』 池田美恵訳 [[中央公論社]] 1972年。
**{{Cite book|和書|date=1996-06|title=ユークリッド原論|edition=縮刷版|isbn=978-4-320-01513-5|ref={{Harvid|ユークリッド|中村ほか|1996}}}}
**{{Cite book|和書|date=2011-05|title=ユークリッド原論|edition=追補版|isbn=978-4-320-01965-2|url=http://www.kyoritsu-pub.co.jp/bookdetail/9784320019652|ref={{Harvid|ユークリッド|中村ほか|2011}}}}
*{{Cite book|和書|editor=[[ヨハン・ルードウィッヒ・ハイベア|ハイベア]]・[[ハインリッヒ・メンゲ|メンゲ]]編|title=エウクレイデス全集|volume=（全5巻）|publisher=[[東京大学出版会]]|url=http://www.utp.or.jp/series/eucleides.html|ref=東大版}} - 「エウクレイデス全集」の世界初の近代語訳。
** 第2巻 [http://www.utp.or.jp/bd/978-4-13-065302-2.html 原論VII－X]、[[斎藤憲]] 訳・解説、2015年8月。ISBN 978-4-13-065302-2
*{{Cite book|author=Euclid|authorlink=ユークリッド|others={{仮リンク|トーマス・L・ヒース|en|Thomas Little Heath}}|year=1956|title=The Thirteen Books of the Elements|volume=Vol. 2 (Books III-IX)|publisher=Dover Publications|isbn=978-0-486-60089-5|url=http://www.perseus.tufts.edu/hopper/text?doc=Euc.+1&redirect=true|ref={{Harvid|Heath|1956}}}}- [http://books.google.com/books?id=lxkPAAAAIAAJ vol. 2]
*{{Cite book|和書|author = [[高木貞治]]|year = 1971|title = 初等整数論講義|edition = 第2版|publisher = [[共立出版]]|location = 東京|ref={{高木|||1970}}}}

== 関連項目 ==
{{Div col}}
*[[算術の基本定理|整数論の基本定理]]
*[[ベズーの等式]]
*[[ユークリッドの互除法]]
*[[有理根定理]]
{{Div col end}}

== 外部リンク ==
*{{MathWorld|title=Euclid's Lemma|urlname=EuclidsLemma}}
{{DEFAULTSORT:ゆうくりつとのほたい}}
[[Category:算術]]
[[Category:数学に関する記事]]
[[Category:数論]]