という、当たり前だろ！？( ・Д・)という定理。素数\(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}\) は整数の集合である。
補題１：\(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'\) を示す。
補題２：\(C'\subset C\) が成り立つ。
証明：\(c\in C\) であり、また補題１より\(\cdots -3c,2c,c,2c,3c,\cdots \in C\)である。（証明終わり）
補題３：\(C\subset C'\) が成り立つ。
証明：\(C\)の要素であるが、\(C'\) の要素でない整数 \(k\) が存在すると仮定する。
この場合も \(k\) を正にすることができる。
このとき、\(k\) を\(c\) で割った余りを \(k'\) とおくともちろん \(k\notin C'\) より \(k'\neq c\)。
また補題１より \(k'\in C\)が成り立つ。
しかしこれは \(C\) の要素のうち絶対値が \(c\) より小さい数ができてしまうことになり、矛盾。
よって \(k\) は存在しない。したがって\(C\subset C'\) が成り立つ。（証明終わり）
したがって、補題２と補題３より、\(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\) の解が存在することが証明された。（証明終わり）
お疲れ様でした。これで、ベズーの等式が成り立つことが証明され、そしてユークリッドの補題も証明されたことになります。本当に数学っていうのは…。当たり前のことをこんなにも回りくどく説明する学問なんですが、そこが面白いんだと思います。
