プロが教える店舗&オフィスのセキュリティ対策術

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

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

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

A 回答 (5件)

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



#3の補足に、「回答後半部分の代数的な方法は知っておりますが」とありましたので、
0+4×1=4
1+1×4=5
4+2×5=14
という方法で、5と14が求められるのは知っているということですよね。

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



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

上記の方法を知っているのなら、a=3が関係ないことは分かっているのでは?
    • good
    • 0
この回答へのお礼

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

お礼日時:2010/09/26 22:54

#2、#3です。



「図を描けば計算しなくてもxとyが求められます」とは、
1×1の4個の正方形を横に並べ、その上に正方形を1個、さらにその横に2個の正方形を、それぞれ辺の長さを合わせて描けば、自動的に5×14の長方形ができます。


#2、#3で説明したのは5と14の求め方を図示しただけで、45×5とか16×14とかを図の中に表したわけではありませんでした。


45×5と16×14を図に示すとしたら、#2の補足欄に書かれているようにa=3という考え方を使うことにして、
45×15と16×42を図示します。

#2の上の図の右下の13×3の部分は、
13×3-12×3=3
#2の上の図の右側の13×16の部分と、下の図の右側の12×15の部分とを、たすきがけで差を求めると、
13×15-16×12=13×(3+12)-(3+13)×12=13×3-12×3=3
さらに全体で見て、45×16と、42×15とを、たすきがけで差を求めると、
45×15-16×42=(16×2+13)×15-16×(15×2+12)=13×15-16×12=3

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

これを図で表すと添付図のようになります。
上の図と下の図の除かれる部分を見ると、右下の1×3の部分以外は、正方形の上部か側部かの違いだけなので大きさは同じです。
よって、除かれる部分の差は3になります。
「Euclidの互除法とAx+By=GCM」の回答画像4

この回答への補足

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

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

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

補足日時:2010/09/26 21:14
    • good
    • 0

#2です。



#2の添付図の上の図と下の図は、位置関係が同じであることが重要であって、大きさを較べることは無意味です。
下の図は、分かりやすいように上の図と同じような大きさで描きましたが、最小の正方形を1×1、全体の大きさを5×14として描いても同じことです。
なので、45×5a-16×14a=a とか、a=3とかという問題ではありません。
単純に、45×5-16×14=1 という意味です。


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

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

45と16を互除法で最大公約数を求めると、
45-16×2=13
16-13×1=3
13-3×4=1
3-1×3=0
という式になります(最大公約数は1)。

上記の式から、2,1,4,3という正方形の数の数列が出てきますが、最後の3を除いて、2,1,4の数列を使って互除法の逆の計算をすれば、
0+4×1=4
1+1×4=5
4+2×5=14
という方法で、5と14が求められます。

(5と14のどちらがマイナスになるかは、互除法の計算回数の偶奇で決まります)

この回答への補足

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

どの部分が45×5で
どの部分が16×14で
どの部分が1なのでしょうか?

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

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

補足日時:2010/09/26 16:30
    • good
    • 0

添付図の上の図は、A=16,B=45の場合の互除法のイメージです。


下の図は、上の図の最小の正方形を除いて、同じ配置で正方形を並べた図です。
下の図の最小の正方形の大きさを1×1とすると、全体の大きさは、5×14になります。
これは、
45×5-16×14=1
を意味しています。
「Euclidの互除法とAx+By=GCM」の回答画像2

この回答への補足

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

下の図での1目盛りは、上の図でのa目盛り分として(今回はa=3)
 45×5a-16×14a=a
というイメージでよろしいしょうか?

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

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

補足日時:2010/09/26 14:08
    • good
    • 0

最後のご質問は


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

この回答への補足

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

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

補足日時:2010/09/25 23:34
    • good
    • 0

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