プロが教えるわが家の防犯対策術!

ユークリッドの互除法で最大公約数が求まる理由がわかりません
どなたか終えてもらってもよろしいでしょうかorz

A 回答 (3件)

わかりません、じゃなくて、何を調べてみたのだけれどここが解りません、と質問しなければなりません。


一般的な証明や説明を並べてみたところで、それが解らないから訊いているのかもしれないのですから。
解らないのに調べてもいないなら、そりゃ解りませんよ。人間ってそんなに優秀じゃ無い。
東大で数学を専攻してます、なんて人なら話は別でしょうけど。
    • good
    • 0

以下のアルファベットは全て自然数である。


a>bで考える。
a/b=c余りd
b/d=e余りf
d/f=gとする。

この時fが最大公約数(のはず)

bとdの公約数をxとした時、bcもdもxで割り切れる。よってaも割り切れる。
なのでbとdの公約数は全てaもbもdも割り切れる。
また。aとbの公約数をyとした時、bc+dもbもyで割り切れる。よってdも割り切れる。
なのでaとbの公約数は全てaもbもdも割り切れる。
つまり、aとbの最大公約数はbとdの最大公約数に等しい。
同様にbとdの最大公約数はdとfの最大公約数に等しい。
dはfの倍数であるので、dとfの最大公約数はfである。
よってaとbの最大公約数もfである。
    • good
    • 1

AとBの最大公約数と、Aと(B-A)の最大公約数が一致するから。

・・・①
 この引き算を何回か繰り返していくのがユークリッドの互除法の本質だよね。

①は
・AとBの最大公約数をCとすると、Cは B-Aの約数でもある。
・Aと(B-A)の公約数は、Bの約数でもある。
から。
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!