ユーグリッドの互除法

質問

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

回答No.4

noname#59057 · ベストアンサー

ん～私の頃（今２８歳ですが）は中学か高校で習ったような気がします。
ですが、今の教育課程からは消えてなくなってたかな？？

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

お礼

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

回答No.3

noname#59057

「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で割り切れる」ということになります。

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

補足

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

回答No.2

noname#59057

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

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

補足

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

回答No.1

relaxador

こんにちは。

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

「ユークリッドの互除法 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である。この方法は《ストイケイア》に書かれているので，ユークリッドの互除法といわれるようになった。」
執筆：丸山 正樹
出典：平凡社　世界大百科事典第二版

ご参考まで。