Euclidの互除法とAx+By=GCM(A,B)となるx,yのイメー

質問

Euclidの互除法とAx+By=GCM(A,B)となるx,yのイメージ
Euclidの互除法のイメージとして、
A×Bの長方形を、なるべく大きな正方形で埋めていくようなイメージで捉えていました。
すると最大公約数が求められるイメージはわかるのですが
x,yがどういう数なのか今一つ掴めません
(代数的にAx+By=GCM(A,B)の式が得られることは理解できています)。

私が思っているようなイメージでなくて結構ですので
互除法のイメージとx,yのイメージが両方掴めるようなモデルをご呈示ください。

また、Euclidの互除法の回数は、最大でも桁数の5倍だそうですが
なぜ10進数表記の桁数、つまり常用対数に依存するのでしょうか?
正確な式は自然対数の2倍くらいだったりするのでしょうか。

回答No.5

nag0720 · ベストアンサー

＞作図の方法によってx,yが求められるのは何故なのでしょうか?

＃３の補足に、「回答後半部分の代数的な方法は知っておりますが」とありましたので、
０＋４×１＝４
１＋１×４＝５
４＋２×５＝１４
という方法で、５と１４が求められるのは知っているということですよね。

この計算式を図で表現しただけです。

＞a=3を使わずに、作図によって求められたものがx,yであると分かる方法はあるのですか?

上記の方法を知っているのなら、a=3が関係ないことは分かっているのでは？

お礼

ありがとうございました。
理解力が無くてすみません。

回答No.4

nag0720

＃２、＃３です。

「図を描けば計算しなくてもｘとｙが求められます」とは、
１×１の４個の正方形を横に並べ、その上に正方形を１個、さらにその横に２個の正方形を、それぞれ辺の長さを合わせて描けば、自動的に５×１４の長方形ができます。

＃２、＃３で説明したのは５と１４の求め方を図示しただけで、４５×５とか１６×１４とかを図の中に表したわけではありませんでした。

４５×５と１６×１４を図に示すとしたら、＃２の補足欄に書かれているようにａ＝３という考え方を使うことにして、
４５×１５と１６×４２を図示します。

＃２の上の図の右下の１３×３の部分は、
１３×３－１２×３＝３
＃２の上の図の右側の１３×１６の部分と、下の図の右側の１２×１５の部分とを、たすきがけで差を求めると、
１３×１５－１６×１２＝１３×（３＋１２）－（３＋１３）×１２＝１３×３－１２×３＝３
さらに全体で見て、４５×１６と、４２×１５とを、たすきがけで差を求めると、
４５×１５－１６×４２＝（１６×２＋１３）×１５－１６×（１５×２＋１２）＝１３×１５－１６×１２＝３

というように、差が常に３になります。

これを図で表すと添付図のようになります。
上の図と下の図の除かれる部分を見ると、右下の１×３の部分以外は、正方形の上部か側部かの違いだけなので大きさは同じです。
よって、除かれる部分の差は３になります。

補足

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

作図によって、x,yを求める方法を示していただいたということなんですね。

よろしければ、もう少し質問させていただきたいのですが
作図の方法によってx,yが求められるのは何故なのでしょうか?
a=3を使わずに、作図によって求められたものがx,yであると分かる方法はあるのですか?

回答No.3

nag0720

＃２です。

＃２の添付図の上の図と下の図は、位置関係が同じであることが重要であって、大きさを較べることは無意味です。
下の図は、分かりやすいように上の図と同じような大きさで描きましたが、最小の正方形を１×１、全体の大きさを５×１４として描いても同じことです。
なので、４５×５a－１６×１４a＝a　とか、a＝３とかという問題ではありません。
単純に、４５×５－１６×１４＝１　という意味です。

＞また、上の図から、下の図を描くのには
＞やはり代数的な方法を使わないといけないのでしょうか?

図を描けば計算しなくてもｘとｙが求められます。
代数的に計算をするとしたら下記のようになります。

４５と１６を互除法で最大公約数を求めると、
４５－１６×２＝１３
１６－１３×１＝３
１３－３×４＝１
３－１×３＝０
という式になります（最大公約数は１）。

上記の式から、２，１，４，３という正方形の数の数列が出てきますが、最後の３を除いて、２，１，４の数列を使って互除法の逆の計算をすれば、
０＋４×１＝４
１＋１×４＝５
４＋２×５＝１４
という方法で、５と１４が求められます。

（５と１４のどちらがマイナスになるかは、互除法の計算回数の偶奇で決まります）

補足

すみません。よくわからないです。

どの部分が４５×５で
どの部分が１６×１４で
どの部分が１なのでしょうか?

回答後半部分の代数的な方法は知っておりますが
「図を描けば計算しなくてもｘとｙが求められます」ですが
計算無しにどうやって縦が5で、横が14だと求められるのですか?
下の図は上の図から1×1の正方形を3個除いた以外に
81個の升目が除かれているように思いますが。

どちらがマイナスになるか関しては仰る見解で結構です。

回答No.2

nag0720

添付図の上の図は、A=16,B=45の場合の互除法のイメージです。
下の図は、上の図の最小の正方形を除いて、同じ配置で正方形を並べた図です。
下の図の最小の正方形の大きさを１×１とすると、全体の大きさは、５×１４になります。
これは、
４５×５－１６×１４＝１
を意味しています。

補足

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

下の図での1目盛りは、上の図でのa目盛り分として(今回はa=3)
　４５×５a－１６×１４a＝a
というイメージでよろしいしょうか?

左辺は理解できたのですが
それが右辺と等しいことがわかるのに
それぞれの図の食み出た部分を数えてしまったのですが
(下の図の3×15から、上の図の1×42を引いた)
それ以外に一発で3とわかる方法はありますか?

また、上の図から、下の図を描くのには
やはり代数的な方法を使わないといけないのでしょうか?

回答No.1

saxan

最後のご質問は
「ラメの定理(Lame's theorem)」かと思いますが
常用対数や自然対数ではなく、
底は黄金比の数φ=(1+√5)/2です。

補足

回答ありがとうございます。
前半の方については如何でしょうか?

また、調べますと
http://www004.upp.so-net.ne.jp/s_honma/euclid/euclid.htm
http://primes.utm.edu/glossary/xpage/LamesTheorem.html
http://www.bookrags.com/research/euclids-algorithm-wom/
定数項部分が微妙に違うのは何故なんでしょう?
黄金比とのことからフィボナッチ数が関係あると思って検索したり
計算してみたりすると、最後のが合ってるような気がするのですが…。
(nが十分に大きい時の話でしょうから、定数項はあまり関係無いのでしょうが…。)