ユークリッドの互除法のもとになる、最大公約数の性質を証明します。
とても原始的です。
割り算(除)じゃなく引き算(差)です。
それどころか、「互」ですらない? 互除法の“互”って何なんでしょうか??
- - - - -
【定理】
A,B,Cは整数とする。
A-B=Cのとき,AとBの最大公約数は、BとCの最大公約数と一致する。
<証明>
AとBの最大公約数をG、BとCの最大公約数とHとする。
A=Ga,B=Gb(a,bは整数)と表せるから、
C=A-B=G(a-b)となり、GはCの約数である。
よって、GはBとCの公約数である。
Hの最大性より、G≦H・・・①
B=Hm,C=Hn(m,nは整数)と表せるから、
A=B+C=H(m+n)となり、HはAの約数である。
よって、HはAとBの公約数である。
Gの最大性より、G≧H・・・②
①②より、G=H (証明おわり)
- - - - -
この定理からすぐ導かれることを系として挙げておきます。
【系1】
A+B=Cのとき、AとBの最大公約数は、BとCの最大公約数と一致する。
Bは整数だから、代わりに-Bにすればよい。引いてることにあまり意味はなく、足してもいいということ。
【系2】
A+B=Cのとき、AとBの最大公約数は、AとCの最大公約数と一致する。
系1で、条件はAとBについて対称だから、AとBを入れ替えればよい。
したがって、A-B=CでもA=B+CでもA-C=Bでもよいのです。
どうせなら左辺にまとめて、
【系3】
A+B+C=0のとき、
AとBの最大公約数、BとCの最大公約数、CとAの最大公約数はすべて等しい。
- - - - -
では、4つにしたらどうか?
【系?】
A+B+C+D=0のとき、
AとBの最大公約数、AとCの最大公約数、AとDの最大公約数、BとCの最大公約数、BとDの最大公約数、CとDの最大公約数はすべて等しい?
これは、
残念ながら無理です。
反例は簡単に作れます。
4-2+1-3=0
4と2の最大公約数は2だが、他のペアでは最大公約数は1になってしまう。
系3で、左辺の項数「3」は特別なのです。
(おわり)