ユーグリッドの互除法

ユーグリッドの互除法の原理はなんですか？？
どうしてそうなるのでしょうか？

No.4 ベストアンサー 回答者： happey 回答日時： 2004/12/05 11:33

ん～私の頃（今２８歳ですが）は中学か高校で習ったような気がします。

ですが、今の教育課程からは消えてなくなってたかな？？

大学では「代数学」のなかで、必ずお目にかかると思います。

この回答へのお礼

そうですか・・・・
いろいろありがとうございました。。

お礼日時：2004/12/05 15:17

No.3 回答者： happey 回答日時： 2004/12/04 20:37

「aをbでわりきることができる」というのは、式でa=b×○」とかけるような整数○が見つかるってことです。

「18＝12×1＋6　から、１２と６をわりきる数（約数）は１８もわりきる」

もし１２と６をわりきる数bが見つかったとします。
すると
　12=b×m　←mは適当な整数
　6=b×n　←nは適当な整数　　と表せることになりますね。
このとき、
　18=12×1+6から、12と6を前の2本の式で書き換えると、
　18=(b×m)×1 + (b×n) = b×(m+n)とできます。
(m+n)は適当な整数同士を足したものだから、整数になるので、
18=b×(m+n)=b×(整数)という式が意味してることは「18はbで割り切れる」ということになります。


という数式的な説明を欲しているわけではないようなきもしますが。。。

この回答への補足

わかりました。ありがとうございます。
このような知識は大学で習うんですか？？

補足日時：2004/12/04 21:15

No.2 回答者： happey 回答日時： 2004/12/04 16:54

原理、、、原理ならここかなぁ。

　http://www.hokuriku.ne.jp/fukiyo/math-obe/euclid …
図を見るとある程度わかると思うんですが、
２つの大きさを構成するできるだけ大きな単位（最大公約数）を作るために、
お互いの大きさを差分を利用して細かく分けていきましょうって感じですかね。


で、それをどう使うかってのはここが詳しいかな。http://www.asahi-net.or.jp/~tt9h-hskw/sugaku/goj …

この回答への補足

１８＝１×１２＋６　から、１２と６をわりきる数（約数）は１８もわりきるし、６＝１８－１×１２　から　１８と１２をわりきる数（約数）は６もわりきるからです。
って書いてあったんですけど、どうしてですか？

補足日時：2004/12/04 18:37

No.1 回答者： relaxador 回答日時： 2004/12/04 14:55

こんにちは。

平凡社ではこのように記しています。

「ユークリッドの互除法 Euclidean algorithm
二つの自然数の最大公約数を見つける方法。二つの自然数 a，b が与えられているとする。a≧bとして，a を b で割ったときの余りを a1とする。bを a1で割り，その余りを b1とおく。b1で a1を割り，余りを a2とする。このようにして，a≧b＞a1＞b1＞a2＞b2＞……となる整数の列が定まっていくが，どこかで0になる。そのすぐ前の自然数が a と bの最大公約数である。例えば，a＝63，b＝49ならば，a＝63，b＝49，a1＝14，b1＝7，a2＝0となり7が最大公約数である(<A REFID="E31500601">図1)。この方法は1変数の多項式にも有効である。1変数の多項式の大きさを次数で比べて，割って余りを取る方法を繰り返せばよい。例えば f＝x4＋x3＋x＋1，g＝2x3＋5x2＋4x＋1の場合g1＝0となり，最大公約式は x2＋2x＋1である。この方法は《ストイケイア》に書かれているので，ユークリッドの互除法といわれるようになった。」
執筆：丸山 正樹
出典：平凡社　世界大百科事典第二版

ご参考まで。