ユークリッドの互除法

質問

すべての自然数a,bに対して
sa+tb=gcd(a,b)
となるような整数s,tがあることの証明問題なのですが、
a=bの場合はs=0, t=1で条件を満たす
a<bとして一般性を失わない
数学的帰納法で
1)
a+b=2
a=b=1なので
s=0, t=1で条件を満たす

2)自然数kに対してa+b≦kで条件を満たすとき、
a+b=k+1のときは
sa+t(b-a)=gcd(a,b-a)
を満たす整数s,tが存在する(a+(b-a)≦kは明らか）
sa+t(b-a)=gcd(a,b-a)
sa+tb-ta=gcd(a,b-a)
(s-t)a+tb=gcd(a,b)

といったかんじで大まかには合ってますか？　間違いがありましたらご指摘ください　　よろしくお願いします

回答No.5

alice_44 · ベストアンサー

← A No.3 補足
それでいいと思う。
(No.4 さんも同じ点を説明してくれているから、
既に解決しているかもしれない。)

No.3 補足のように改訂すると、
帰納法の漸化ステップで a = b-a が発生しても
ひとつ先の k でそれを捕捉することができ、
a < b という仮定が破れて漸化できなくなることが避けられる。

書き方という面では、
＞ a+b=k+1のときは
＞ sa+t(b-a)=gcd(a,b-a)
＞ を満たす整数s,tが存在する
も、やや唐突な感がある。

a + (b-a) ≦ k から、帰納法の仮定によって
s a + t (b-a) = gcd(a,b-a) を満たす s,tが存在する
のだということ、そして
gcd(a,b-a) = gcd(a,b) から
(s-t) a + t b = gcd(a,b) となるのだということを
話の流れが見やすいように書いた方がいい。

もちろん、gcd(a,b-a) = gcd(a,b) の証明を添えるべき
であることも、No.1 に言われたとおり。

お礼

回答ありがとうございます。証明でどこまでかくかとかどういう風に書くといいかとかよくわからないんですけど、そういうのは解答解説などをよんだりして慣れていくしかないんでしょうか？

回答No.4

kabaokaba

ん・・・いろいろあるんだけど

記号は同じものを使うことにしよう

No.1の「お礼」より
>つまりgにはGより多く同じ素因数もしくはGとは違う素因数が含まれていない

これは何を言ってるのかとても分かりにくい．あってるんだけど・・・
結局，

gはb-aの約数で，gはaの約数だから
gはbの約数にもなって，つまり, gはaとbの約数
a,bの約数はgcd(a,b)=Gの約数なので，gはGの約数

こういうことでしょう．
＃記号「|」を使えばもっと整理できる

同様にして
Gはgの約数となるので，よって g=G

とこうなるわけですよね．

==========
私はこれで本質的な部分はクリアだと思うけど，
証明として「きちんとする」には，まだまだ不足というか
論証が甘いと思います．
それはalice_44さんが指摘している通りですし，
もっと整理するならば
「a+bの値で帰納法」という枠組み
そのものにもメスを入れるほうがよいようにも思う．
＃私の好みだと gcd(a,b)=1と仮定して，
＃楽なケースを先に処理するようにする

まあ，好みですが，
ユークッリドの互除法の「アルゴリズム」を考えると
帰納法のように「階段を登る」よりも
「自然数の降下」を考えるほうが
すっきりするのではないかと思います

ついでにいうと
gcd(a,b-a)=gcd(a,b)はもっと一般化できて

任意の整数a,b,kに対して
gcd(a, b+ka)=gcd(a,b)
が成り立つ．
これは結局のところ

任意の整数a,bに対して
b=ka+r（r=0,1,...,a-1）（割り算そのもの）
としたとき，
gcd(a,b) = gcd(a,r)

という「普通の教科書にでてる形」になります．
そして，これが互除法の本質です．

=========
おまけ：
a=bの場合をOKとして
a<bを仮定して，その中で
帰納法の段階を追っていくときに
aとb-aでの話がでてきてるけど
これに対して，つねに a<b-aであるとは限りません
しかし，帰納法の外側で a<b を仮定しているので
例えば
a=b-a（ようは aがbの半分のとき,）
は帰納法の枠組みからはずれてしまいます．
したがって，「帰納法の仮定」を適用することはできません．

こういう場合をさらに場合わけで処理しようとすると，
不安定な論理展開になるでしょう．

お礼

回答ありがとうございます。
>
これは何を言ってるのかとても分かりにくい．あってるんだけど・・・
結局，

gはb-aの約数で，gはaの約数だから
gはbの約数にもなって，つまり, gはaとbの約数
a,bの約数はgcd(a,b)=Gの約数なので，gはGの約数

確かにこっちのほうがずっとすっきりしてますね。参考にしてみます。

>しかし，帰納法の外側で a<b を仮定しているので
例えば
a=b-a（ようは aがbの半分のとき,）
は帰納法の枠組みからはずれてしまいます

これは、gcd(a,b-a)の話が、a<b-aじゃないと崩れてしまうということでしょうか？　gcd(x,y)=gcd(y,x)といった風に入れ替えられることを前もって説明すれば回避できますか？

回答No.3

alice_44

a=b か a＜b かで場合分けしてから
a＜b の場合に帰納法を行うみたいな
書き方になってしまっているが、
本当は、帰納法のほうが外側にあって、
漸化のとき b-a が 0 にならないように
a=b と a＜b で場合分けしているはず。
そうでないと、a+b=2 のとき a=b であることや、
a＜b のとき a=b-a になるかもしれないことと
話が合わない。
もう少し流れを整理して書かないと、
スジが解ってない疑いをかけられるよ。

お礼

回答ありがとうございます。

最初の場合わけの文を消して
質問文中の(2)を以下のように変えれば
>　a+b=2 のとき a=b であることや、
については下記の文にすれば対応できてますか？
>　a＜b のとき a=b-a になるかもしれないことと
これについてはいまいち問題点がわからなかったので、もうすこし説明してくださいますか？

======================================
2)自然数kに対してa+b≦kで条件を満たすとき、

a+b=k+1となるようなa,bについて考える。
a=bの場合はs=0, t=1で条件を満たすので、
a<bとして一般性を失わない
=======================================

回答No.2

alice_44

a=b か a＜b かで場合分けしてから
a＜b の場合に帰納法を行うみたいな
書き方になってしまっているが、
本当は、帰納法のほうが外側にあって、
漸化のとき b-a が 0 にならないように
a=b と a＜b で場合分けしているはず。
そうでないと、a+b=2 のとき a=b であることや、
a＜b のとき a=b-a になるかもしれないことと
話が合わない。
もう少し整理して書かないと、
解ってない疑いをかけられるよ。

回答No.1

kabaokaba

>といったかんじで大まかには合ってますか？　

あってないです．

gcd(a,b-a)=gcd(a,b)

をどうやって証明しますか？
これが本質です．

お礼

入力が面倒くさいのでgcd(a,b-a)=g, gcd(a,b)=Gとします

1.
(b-a)/g=(b/g)-(a/g)

左辺とa/gが整数なのでb/gも整数　bはgで割り切れる

つまりgにはGより多く同じ素因数もしくはGとは違う素因数が含まれていない

2.
(b-a)/G=b/G -a/G

G=gcd(a,b)より右辺が整数になるのは明らか　よってb-aはGで割り切れる。

つまりGにはgより多く同じ素因数もしくはgとは違う素因数が含まれてることはない。

1, 2が同時に条件を満たすのはg=Gのときだけだからg=G