ユークリッドの補題

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

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

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

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

例

たとえば、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 で割り切れる。

反例

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

定式化

p を素数とし、2 つの整数 a, b の積 ab は p で割り切れるとする（このことは記号的に p ${\displaystyle \mid }$ ab と表す。これの否定は p ${\displaystyle \nmid }$ ab と表され、ab が p で割り切れないことを示す）。このとき p ${\displaystyle \mid }$ a または p ${\displaystyle \mid }$ b、あるいはその両方が成り立つ。

${\displaystyle 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).}$

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

• p ${\displaystyle \nmid }$ a かつ p ${\displaystyle \nmid }$ b ならば p ${\displaystyle \nmid }$ ab

${\displaystyle p\nmid a\land p\nmid b\Rightarrow p\nmid ab}$

• p ${\displaystyle \nmid }$ a かつ p ${\displaystyle \mid }$ ab ならば p ${\displaystyle \mid }$ b

${\displaystyle p\nmid a\land p\mid ab\Rightarrow p\mid b}$

一般化

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

定理 ― c が a と互いに素であり、かつ c ${\displaystyle \mid }$ ab ならば、c ${\displaystyle \mid }$ b である。

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

• c ${\displaystyle \mid }$ a
• c は a と互いに素のため c ${\displaystyle \nmid }$ a、従って c ${\displaystyle \mid }$ b

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

証明

ベズーの補題による証明

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

${\displaystyle rx+sy=1}$

(1)

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

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

${\displaystyle rc+sa=1.}$

(2)

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

${\displaystyle rcb+sab=b}$

(3)

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

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

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

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

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

${\displaystyle ac=lg}$

の関係がある。…③

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

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

ここでユークリッドの補題の前提条件として ${\displaystyle a,c}$ が互いに素であり、かつ ${\displaystyle c\mid ab}$ のとき， ${\displaystyle ab}$ は ${\displaystyle c}$ の倍数かつ、当然 ${\displaystyle a}$ の倍数であるから、${\displaystyle ab}$ は ${\displaystyle a,c}$ の公倍数． ④より ${\displaystyle lcm(a,c)=ac}$ で①より ${\displaystyle ac\mid ab}$．ゆえに ${\displaystyle c\mid 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]。

証明

素数 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 を割り切る。
これが証明すべきことであった[8]。

脚注

注釈

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

出典

1. (ハーディ & ライト 2012, p. 27)
2. (高木 1971, 第1章)
3. (ユークリッド & 中村ほか 1996, pp. 162f)
4. (ユークリッド & 中村ほか 1996, pp. 163f)
5. (ユークリッド & 中村ほか 1996, pp. 164f)
6. (ユークリッド & 中村ほか 1996, p. 169)
7. (ユークリッド & 中村ほか 1996, pp. 169f)
8. (Heath 1956, pp. 331f)

参考文献

• 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巻の最初の邦訳。
  • 『ユークリッド原論』（ハードカバー）、1971年7月。ISBN 978-4-320-01072-7。 
    • （抜粋）『世界の名著9』 池田美恵訳 中央公論社 1972年。
  • 『ユークリッド原論』（縮刷版）、1996年6月。ISBN 978-4-320-01513-5。 
  • 『ユークリッド原論』（追補版）、2011年5月。ISBN 978-4-320-01965-2。 
• ハイベア・メンゲ 編『エウクレイデス全集』 （全5巻）、東京大学出版会。  - 「エウクレイデス全集」の世界初の近代語訳。
  • 第2巻 原論VII－X、斎藤憲 訳・解説、2015年8月。ISBN 978-4-13-065302-2
• 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。 

関連項目

• 整数論の基本定理
• ベズーの等式
• ユークリッドの互除法
• 有理根定理

外部リンク

• 『{{{2}}}』 - 高校数学の美しい物語
• ユークリッドの補題の証明
• Weisstein, Eric W. "Euclid's Lemma". mathworld.wolfram.com (英語).