ユークリッドの補題

代数学と数論において、ユークリッドの補題は素数の基本的な性質を捉えた補題である: ^{[注 1]}

たとえば、p = 19、a = 133、b = 143の場合、ab = 133 × 143 = 19019となり、これは 19 で割り切れるので、補題は 133 または 143 のどちらかまたは両方が 19 で割り切れることを意味します。実際、133 = 19 × 7です。

この補題はユークリッドの『原論』で初めて登場し、初等数論における基本的な結果である。

補題の前提が成り立たない場合、つまりp が合成数である場合、その結果は真または偽のいずれかになります。たとえば、 p = 10、a = 4、b = 15の場合、合成数 10 はab = 4 × 15 = 60を割り切りますが、 10 は 4 も 15 も割り切りません。

この性質は算術の基本定理の証明の鍵となる。^{[注 2]これは}素数元を定義するために使用され、素数は任意の可換環に一般化される。ユークリッドの補題は、整数では既約元も素元であることを示す。この証明は帰納法を使用するため、すべての整数領域に適用されるわけではない。

ユークリッドの補題は、通常、次の同値形式で使用されます。

ユークリッドの補題は、素数から任意の整数まで次のように一般化できます。

これは一般化です。素数p が整数aと互いに素となるのは、 p がa を割り切れない場合のみです。

この補題はユークリッドの『原論』第7巻の命題30として初めて登場する。この補題は初等整数論を扱うほぼすべての書籍に含まれている。^{[4] [5] [6] [7] [8]}

補題の整数への一般化は、1681 年にジャン プレステの教科書Nouveau Elémens de Mathématiquesに登場しました。 ^[9]

カール・フリードリヒ・ガウスの論文『算術論』では、補題の記述はユークリッドの命題14（第2節）であり、ガウスはこれを用いて整数の素因数の分解積の一意性（定理16）を証明し、その存在を「自明」と認めている。この存在と一意性から、ガウスは素数の整数への一般化を演繹している。^[10]このため、ユークリッドの補題の一般化はガウスの補題と呼ばれることもあるが、この用法はガウスの平方剰余に関する補題と混同されるため誤りであると考える者もいる^[11]。

最初の 2 つのサブセクションは、ユークリッドの補題の一般化されたバージョンの証明です。つまり、n がab を割り切り、aと互いに素である場合、 b を割り切るということです。

元のユークリッドの補題は直ちに成り立ちます。なぜなら、nが素数であれば a を割り切れるからです。割り切れない場合は a と互いに素なので、一般化されたバージョンではb を割り切れます。

現代数学では、ベズーの等式が一般的な証明として挙げられるが、これはユークリッドの時代には知られていなかった。^[12]ベズーの等式は、xとyが互いに素な整数（つまり、1と-1以外に共通の約数を持たない）であれば、 rとsという 整数が存在し、

${\displaystyle rx+sy=1.}$

aとn が互いに素で、n | ab であるとする。ベズーの恒等式により、 rとsが存在し、

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

両辺にbを掛けます。

${\displaystyle rnb+sab=b.}$

左辺の第 1 項はnで割り切れ、第 2 項はabで割り切れますが、仮定により ab はnで割り切れます。したがって、それらの合計bもnで割り切れます。

次の証明は、減算のみを使用して進行するユークリッドのユークリッド互除法のバージョンに触発されています。

であり、nとa が互いに素（つまり、最大公約数が1）であると仮定します。 n がb を割り切れることを証明する必要があります。となる整数qが存在するので、一般性を失うことなく、n、q、a、およびb は正であると仮定できます。これは、割り切れる関係が関係する整数の符号に依存しないためです。 ${\displaystyle n\mid ab}$${\displaystyle n\mid ab,}$${\displaystyle nq=ab.}$

これを強い帰納法で証明するために、 abのより低いすべての正の値に対して結果が証明されていると仮定します。

3つのケースがあります:

n = aの場合、互いに素であることからn = 1となり、n はb を自明に割り切れます。

n < aの場合、

${\displaystyle n(qb)=(an)b.}$

正の整数a – nとnは互いに素です。つまり、それらの最大公約数d はそれらの和を割り切るため、nとa の両方を割り切ります。互いに素であるという仮説により、 d = 1となります。したがって、 0 < ( a – n ) b < abであるため、帰納法の仮説から結論が導かれます。

同様に、n > aの 場合には

${\displaystyle (na)q=a(bq),}$

また、同じ議論から、n – aとaは互いに素であることが示されます。したがって、0 < a ( b − q ) < abとなり、帰納法の仮定はn − a がb − q を割り切ることを意味します。つまり、ある整数に対してです。したがって、およびをn − aで割ると、次の式が得られます。したがって、およびをaで割ると、目的の結果 が得られます。${\displaystyle bq=r(na)}$${\displaystyle (na)q=ar(na),}$${\displaystyle q=ar.}$${\displaystyle ab=nq=anr,}$${\displaystyle b=nr,}$

ユークリッドの補題はユークリッドの『原論』第7巻の命題30で証明されている。原論の証明はそのままでは理解しにくいので、ユークリッドの解説(1956, pp. 319–332)を引用する。

提案19

4 つの数が比例する場合、最初の数と 4 番目の数から生成される数は、2 番目の数と 3 番目の数から生成される数に等しくなります。また、最初の数と 4 番目の数から生成される数が、2 番目の数と 3 番目の数から生成される数に等しい場合、4 つの数は比例します。^{[注 3]}

提案20

同じ比率を持つものの最小数は、同じ比率を持つものを同じ回数測定します。大きいほど大きく、小さいほど小さくなります。^{[注 4]}

提案21

互いに素な数は、その数と同じ比を持つ数の中で最小の数である。^{[注 5]}

提案29

いかなる素数も、それが測定していないいかなる数とも素である。^{[注 6]}

提案30

2つの数を掛け合わせると同じ数になり、その積を素数で測ると、元の数のうちの1つも測られる。^{[注 7]}

30の証明

cが素数で、ab を測定する場合、c はaまたはb を測定します。c がa を測定しないと
仮定します。したがって、cとa は互いに素です。
［第七章 29］
ab＝mcと仮定します。
したがってc  : a＝b : mです。 ［第七章 19］
したがって［VII. 20, 21］b＝ncであり、nは整数である。
したがってc はb を測定する。
同様に、c がb を測定しない場合、c はa を測定する。
したがってc は2 つの数a、bのいずれかを測定する
。QED ^[18]

• バイノック、ベラ（2013）、抽象数学への招待、数学の学部テキスト、シュプリンガー、ISBN 978-1-4614-6636-9。
• ユークリッド（1956年）『13元素論』第2巻（第3巻から第9巻）、ヒース、トーマス・リトル訳、ドーバー出版、ISBN 978-0-486-60089-5- 第2巻
• Euclid (1994)、Les Éléments、traduction、commentaires et Notes (フランス語)、vol. 2、バーナード・ヴィトラック訳、338–339ページ、ISBN 2-13-045568-9
• ガウス、カール・フリードリヒ（2001）、Disquisitiones Arithmeticae、クラーク、アーサー・A（第2版、訂正版）訳、コネチカット州ニューヘイブン：エール大学出版局、ISBN 978-0-300-09473-2
• Gauss, Carl Friedrich (1981)、Untersuchungen uber hohere Arithmetik [高等算術の研究]、Maser, H. 訳 (第 2 版)、ニューヨーク: チェルシー、ISBN 978-0-8284-0191-3
• ハーディ、GH、ライト、EM、ワイルズ、AJ（2008-09-15）、数論入門（第6版）、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-921986-5
• アイルランド、ケネス、ローゼン、マイケル（2010）、現代数論への古典的入門（第2版）、ニューヨーク：シュプリンガー、ISBN 978-1-4419-3094-1
• ジョイナー、デイビッド、クレミンスキー、リチャード、トゥリスコ、ジョアン（2004）、応用抽象代数、JHU プレス、ISBN 978-0-8018-7822-0。
• ランドー、エドマンド（1999）、初等数論、グッドマン、JE訳（第2版）、プロビデンス、ロードアイランド：アメリカ数学会、ISBN 978-0-821-82004-9
• マーティン、GE（2012）、幾何学と非ユークリッド平面の基礎、数学の学部テキスト、シュプリンガー、ISBN 978-1-4612-5725-7。
• リーゼル、ハンス（1994）、素数と因数分解のためのコンピュータ手法（第2版）、ボストン：ビルクハウザー、ISBN 978-0-8176-3743-9。

• Weisstein, Eric W.「ユークリッドの補題」。MathWorld。