証明

記号を整理して見通しを良くするために$X=\gcd(a,b)$, $Y = \gcd(a, b-a)$, $Z = \gcd(a, b+a)$と置きましょう｡

まず最初に\(a=0\), \(b=0\)のときは\(X, Y, Z\)のどれもが\(\gcd(0, 0)\)となるので示したい等式は成り立ちます｡ そこで\(a\)または\(b\)の少なくともどちらか一方がゼロでない整数の場合を考えましょう｡

それでは1つ目の等号(X=Y)を証明してみましょう｡ \(X\)は\(a\)と\(b\)の(最大)公約数なので, \(a=Xc\), \(b=Xd\)となる整数\(c, d\)が存在します｡ すると, \[b-a=Xd-Xc=X(d-c)\] と変形できることから\(X\)は\(b-a\)も割り切ることがわかります｡ つまり\(X\)は\(a\)と\(b-a\)の公約数であることがわかります｡ もちろん公約数は最大公約数以下なので\(X\leq Y\)となることがわかりました｡

今度は\(Y\)に注目します｡ \(Y\)は\(a\)と\(b-a\)の(最大)公約数であるから\(a=Ye\), \(b-a=Yf\)となる整数\(e, f\)が存在します｡ これらの等式を使うと \[b=Yf+a=Yf+Ye=Y(f+e)\] と書けることから\(Y\)が\(b\)も割り切ることがわかります｡ つまり\(Y\)は\(a\)と\(b\)の公約数ということです｡ 公約数は最大公約数以下であるから\(Y\leq X\)を得ます｡

さて以上の議論で2つの不等号\(X\leq Y\)と\(Y\leq X\)を得ました｡ これより\(X=Y\)が導かれます｡ \(X\)と\(Y\)を元に戻すと証明したかった等号\(\gcd(a,b) = \gcd(a, b-a)\)が得られます｡

以上で1つ目の等号の証明を終わりにしたいと思います｡ 2つ目の等号も同様の議論で証明できるので, 演習問題として残しておきますので, ぜひご自分の手を動かして証明を書いてみてください｡

補足: 上の証明で最大公約数にカッコをつけている箇所がありましたね｡ どういう意味かというと, もちろん\(X\)は最大公約数なのですが, そこでは最大であるという性質ではなく, ｢公約数である｣という事実から次の結論が導かれているのでカッコをつけました｡ カッコをつけなくても間違ってはいないし, そもそも｢(最大)｣を省いてしまっても大丈夫です｡

証明

もし\(n\)がゼロの場合は証明したい式が成り立つことは自明なので\(n \neq 0\)と仮定して話を進めましょう｡ 次に\(n\)の正負によって場合分けをしておきましょう｡ まずは\(n\)が正の整数の場合を考えていきます｡

上で\(\gcd(a,b) = \gcd(a, b-a)\)はすでに証明済みです｡ この等号の左辺の\(b\)を\(b-a\)にして適用すると\(\gcd(a,b-a) = \gcd(a, b-2a)\)が得られます｡ 同様に, 始めの式の\(b\)を\(b-2a\)にして適用して\(\gcd(a,b-2a) = \gcd(a, b-3a)\)が得られる｡ この議論を繰り返すと \[\gcd(a,b-a) = \gcd(a, b-2a)=\gcd(a, b-3a)=\cdots = \gcd(a, b-na)\] となり, いずれ\(b-na\)に到達し等号の最初と最後を比べると証明したかった等式\(\gcd(a, b)=\gcd(a, b-an)\)が得られます｡

最後に\(n\)が負の整数の場合を考えます｡ \(n=-n’\), \(n’\)は正の整数, と置きます｡

最大公約数の性質その1で\(\gcd(a,b) = \gcd(a, b+a)\)を証明しました｡ これを利用しましょう｡ この式の\(b\)を\(b+a\), \(b+2a, \cdots, b+n’a\)として適用すると \[\gcd(a, b) = \gcd(a, b+a)=\gcd(a, b+2a)=\cdots = \gcd(a, b+n’a)\] \(n’=-n\)なので\(\gcd(a, b)=\gcd(a, b-na)\)となり証明したかった等号が得られたことになります｡

以上で証明を終了したいと思います｡

証明

第一段階として要求をみたすような整数\(q,r\)が存在することを示します｡

議論を簡単にするためにまず\(a, b\)が正の整数と仮定してみましょう｡

次のような集合\(S\)を考えます｡ \[ S= \{ n \in \Z \mid a-bn \geq 0 \}.\] この集合は\(a-bn\)がゼロ以上になるような整数\(n\)からなる集合です｡ 例えば, \(n=0\)とすると\(a-bn=a>0\)となる｡ (今\(a>0\)と仮定していることを思い出しましょう｡) なので, \(0\in S\)となる｡ (\(0\)は集合\(S\)の要素ということを表す記号でしたね｡)

集合\(S\)に入っているどんな整数\(n\)を取ってきても\(a-bn \geq 0\)を満たしていることから\(n \leq a/b\)であることがわかる｡ つまり\(S\)に入っている整数はどんなに大きくても高々\(a/b\)までということがわかる｡ これらから言えることは集合\(S\)は空集合でなく, 上界を持つということです｡ そこで\(q\)を\(S\)に属する整数の中で最大のものとしましょう｡ そして\(r=a-bq\)と置きます｡ \(q\)の定め方から\(r\geq 0\)がわかります｡ 変形すると$a=bq+r$となっているので, 後は\(r < b\)がわかれば第一段階の目標達成です｡

これを証明するために, \(r \geq b\)と仮定してみましょう｡ つまり\(r -b \geq 0\)を仮定します｡ すると \[0 \leq r- b = a – bq – b = a-b(q+1) \] が成り立ちます｡ これより\(q+1 \in S\)となることがわかります｡ しかし, \(q\)が\(S\)に属する元の中で最大のものでしたからそれよりも大きい\(q+1\)が\(S\)に属するのは矛盾となるわけです｡ この矛盾は\(r \geq b\)と仮定したことから生じたものなのでこの仮定が間違っていた, つまり\(r < b\)であることが証明されました｡

まとめると\(a=bq+r\)で\(0\leq r < b\)となる\(q\)と\(r\)が見つかったことになります｡ これで第一段階終了です｡

第二段階では, 一意性を証明して定理の証明を完成させたいと思います｡ 一意性を証明するためには第一段階で発見した\(q, r\)以外には条件をみたす整数は存在しないことを証明できればOKです｡

そこで\(q’, r’\)を\(a=bq’+r’\), \(0 \leq r’ <b\)を満たす整数としてみましょう｡ 目標はこれらが上で得た\(q, r\)と一致することです｡

始めに\(r’=a-bq’ \leq 0\)と書くと\(q’ \in S\)であることがわかります｡ \(q\)が\(S\)の最大元であったことから\(q’ \leq q\)がわかります｡ ここでもし\(q=q’\)であれば \[ r’ = a-bq’ = a-bq =r\] となり\(r’=r\)も得られるので, \(q'<q\)と仮定してみましょう｡ \(q\)も\(q’\)も整数なのでその差は\(1\)以上です｡ なので\(m=q-q’\)とすれば\(m \geq 1\)となります｡ \(r’\)の大きさを評価してみましょう｡

\[ r’ = a-bq’ =a-b(q-m) =a-bq+bm = r +bm \geq b,\] ここで最後の不等式には\(r \geq 0\)と\(m \geq 1\)を用いました｡ ここで得られた結果\(r’ \geq b\)は\(r’\)の取り方に矛盾しています｡ ということで\(q'<q\)と仮定したことが誤り, つまり\(q’=q\)でなければならないことがわかりました｡

以上で\(q’=q, r’=r\)であることを証明できたので, 条件をみたすものは一組しかないことが証明できました｡

これまでの証明は\(a, b\)が正の整数と仮定しましたが, どちらかまたは両方が負の整数でも似たような議論ができます｡ 実際は\(a\)の値に証明はさほど左右されず, \(b\)が負の場合は集合\(S\)の最大元を考える代わりに最小元を考えることによって証明を書き換えることができます｡ なので後は演習問題としますのでぜひ試みてください｡

これで証明を終わりにしたいと思います｡

ユークリッドの互除法の証明

まず初めに\(b=0\)の場合を考えてしまいましょう｡ この場合は\(\gcd(a,0)=a\)ですから\(m=0,n=0\)とすれば式\(g= ma+nb\)を満たすことがわかります｡ そこで\(b\neq 0\)の場合を考えていきましょう｡

証明のキーは最大公約数その2で証明した性質です｡ その定理の\(a, b\)を入れ替えて適用すると \[ \gcd(a, b) = \gcd(b, a-bn), \] \(n\)は任意の整数となります｡

整数の除法の定理より \[a=bq_1+r_1, 0\leq r_1 <|b|\] を満たす整数\(q_1, r_1\)が一意的に存在します｡ 上の性質を使うと \[\gcd(a, b)= \gcd(b, a-bq_1)= \gcd(b, r_1)\] となります｡ つまり, \(a,b\)の最大公約数は割る数\(b\)と余り\(r_1\)の最大公約数に等しいことがわかります｡

さて, もしここで\(r_1=0\)なら\(\gcd(a, b)=\gcd(b, r_1)=b\)となるので\(m=0, n=1\)と取ればよいですね｡

\(r_1\neq 0\)ならば今度は \[b=r_1q_2+r_2, 0\leq r_2 <|r_1|\] を満たす整数\(q_2, r_2\)が存在します｡ 最大公約数の性質その2をもう一度使うと \[ \gcd(a, b)=\gcd(b, r_1) = \gcd(r_1, b-r_1q_2)=\gcd(r_1, r_2)\]

もし\(r_2=0\)なら, ここで一旦ストップし, もしも\(r_2\neq 0\)ならばもう一度整数の除法を適用して \[r_1=r_2q_3+r_3, 0\leq r_3 <|r_2|\] となる整数\(q_3, r_3\)が存在します｡ このように余りがゼロでない限り割る数を余りで割るということを繰り返します｡ もし余りがゼロにならなかったらこの作業を永遠に繰り返さなければいけないませんが, 幸いなことに余り\(r_i\)は一回ごとに絶対値が確実に小さくなっていってます｡ これは\(0\leq r_i <|r_{i-1}|\)のおかげです｡ つまりこの作業は有限回繰り返すことでいつかは余りをゼロにすることができるということです｡

そこで, 余りがゼロになるところを書いてみると \[\begin{align*}
r_{k-2} &= r_{k-1}q_k+r_k && 0\leq r_k <|r_{k-1}|\\
r_{k-1} &= r_{k}q_{k+1}+0
\end{align*}\]

最大公約数の性質その2の繰り返し適用すると \[\gcd(a, b)=\gcd(b, r_1)=\gcd(r_1, r_2)=\cdots = \gcd(r_{k-1}, r_k) = \gcd(r_k, 0)= r_k\] となることがわかります｡ さて, \(\gcd(a, b)=r_k\)がわかりましたから次は \(r_k=ma+nb\)となる\(m\)と\(n\)を見つけましょう｡

最初の除法の式より\(r_1=a+(-q_1)b\)と書けます｡ これは\(a\)と\(b\)の線形結合ですね｡ これを2つめの除法の式の\(r_1\)に代入すると \[\begin{align*}
r_2 &= b-q_2r_1\\
&=b-q_2(a+(-q_1)b)\\
&=(-q_2)a+(q_1q_2+1)b
\end{align*}\] が得られます｡ これもまた\(a\)と\(b\)の線形結合です｡

これを順次繰り返していくと次の\(r_i\)も\(a\)と\(b\)の線形結合で書けるから最後の\(r_k\)も\(a\)と\(b\)の線形結合で書けることがわかります｡ \(r_k=\gcd(a,b)\)であったからこれで証明が終了となります｡