読者です 読者をやめる 読者になる 読者になる

数学徘徊記

自由な数学ブログ。

ユークリッドの補題の証明

数学 整数論

まず、ユークリッド補題とは…。

素数\(p\)が\(ab\)を割り切るなら,\(p\)は\(a\)か\(b\)のいずれか一方を割り切る。

という、当たり前だろ!?( ・Д・)という定理。

しかしこれ、証明がかなり回りくどい…。
なかなか完全な証明を書いていないところが多かったので、書きます。

これ、まずベズーの等式を証明することから始まります。
ベズーの等式とは…。

\(a\)と\(b\)を 0 でない整数とし、\(d\) をそれらの最大公約数とする。このとき \(ax+by=d\) の整数解 \(x\) と \(y\) が存在する。さらに、i) \(d\) は \(ax+by\) と書ける最小の正の整数であり、ii)\(ax+by\)の形のすべての整数は\(d\) の倍数である。


これがなぜユークリッド補題につながるのか、最初に証明しておきます。

証明
\(ab\) が p で割り切れ、 \(a\) が \(p\) で割り切れないとする。
この時、\(a\) と \(p\) の最大公約数は1より、
ベズーの等式より、\(ax+py=1\) となる整数解 \((x,y)\) が存在する。
このとき、上の式の両辺に \(b\) をかけて \(abx+bpy=b\) となる。
ここで、\(abx\) と \(bpy\) は両方 \(p\) の倍数より、\(b\) も \(p\) の倍数である。
よってベズーの等式が成り立つとき、ユークリッド補題が成り立つことが証明された。

ということで、ベズーの等式を証明すれば、ユークリッド補題も証明したことになります。

しかし、このベズーの等式が面倒くさい…。
難しめですが、頑張ってください。

証明
\(C\left\{ax+by|x\in\mathbb{Z},y\in\mathbb{Z}\right\}\) を定義する。このとき、\(\mathbb{Z}\) は整数の集合である。

補題1:\(C\)は加法に閉じている。
証明:\(C\)の要素を \(c_1,c_2\) とし、\(c_1=ax_1+by_1,c_2=ax_2+by_2\) と表せるとする。
このとき\(c_1+c_2=a(x_1+x_2)+b(y_1+y_2)\) となり、明らかに \(c_1+c_2\in C\)である。(証明終わり)

また、\(C\) の要素のうち絶対値が最小のものを\(c\)とする。必要な時に応じて、\(x\) と \(y\) の符号を
両方変えることによって、\(c\) を正にすることができる。
また、\(c\) の倍数の集合を \(C'\) とする。
このとき、\(C=C'\) を示す。 

補題2:\(C'\subset C\) が成り立つ。
証明:\(c\in C\) であり、また補題1より\(\cdots -3c,2c,c,2c,3c,\cdots \in C\)である。(証明終わり)

補題3:\(C\subset C'\) が成り立つ。
証明:\(C\)の要素であるが、\(C'\) の要素でない整数 \(k\) が存在すると仮定する。
この場合も \(k\) を正にすることができる。
このとき、\(k\) を\(c\) で割った余りを \(k'\) とおくともちろん \(k\notin C'\) より \(k'\neq c\)。
また補題1より \(k'\in C\)が成り立つ。
しかしこれは \(C\) の要素のうち絶対値が \(c\) より小さい数ができてしまうことになり、矛盾。
よって \(k\) は存在しない。したがって\(C\subset C'\) が成り立つ。(証明終わり)

したがって、補題2と補題3より、\(C=C'\) が成り立つことが示された。
すなわち、\(C\) の要素(\(ax+by\) で表される数)はすべて \(c\) の倍数である。

ここから、\(c\) がどのような数かを考察する。

もちろん\(a\in C,b\in C\) より、\(c\) は \(a\) と \(b\) の公約数である。
また \(ax+by=c\) が解をもつので、\(c\) は \(a\) と \(b\) の最大公約数で割り切れなければいけない。
よって \(c\) は \(a\) と \(b\) の最大公約数であり、\(c=d\) が成り立つ。

したがって、\(ax+by=d\) の解が存在することが証明された。(証明終わり)


お疲れ様でした。これで、ベズーの等式が成り立つことが証明され、そしてユークリッド補題も証明されたことになります。本当に数学っていうのは…。当たり前のことをこんなにも回りくどく説明する学問なんですが、そこが面白いんだと思います。