Euclidの互除法とAx+By=GCM(A,B)となるx,yのイメージ
- Euclidの互除法のイメージとして、A×Bの長方形を、なるべく大きな正方形で埋めていくようなイメージで捉えていました。
- 互除法のイメージとx,yのイメージが両方掴めるようなモデルをご呈示ください。
- Euclidの互除法の回数は、最大でも桁数の5倍だそうですが、なぜ10進数表記の桁数、つまり常用対数に依存するのでしょうか？
- ベストアンサー
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倍くらいだったりするのでしょうか。
- sak_sak
- お礼率14% (194/1334)
- 数学・算数
- 回答数5
- ありがとう数2
- みんなの回答 （5）
- 専門家の回答
質問者が選んだベストアンサー
＞作図の方法によってx,yが求められるのは何故なのでしょうか? ＃３の補足に、「回答後半部分の代数的な方法は知っておりますが」とありましたので、 ０＋４×１＝４ １＋１×４＝５ ４＋２×５＝１４ という方法で、５と１４が求められるのは知っているということですよね。 この計算式を図で表現しただけです。 ＞a=3を使わずに、作図によって求められたものがx,yであると分かる方法はあるのですか? 上記の方法を知っているのなら、a=3が関係ないことは分かっているのでは？
その他の回答 (4)
- nag0720
- ベストアンサー率58% (1093/1860)
＃２、＃３です。 「図を描けば計算しなくてもｘとｙが求められます」とは、 １×１の４個の正方形を横に並べ、その上に正方形を１個、さらにその横に２個の正方形を、それぞれ辺の長さを合わせて描けば、自動的に５×１４の長方形ができます。 ＃２、＃３で説明したのは５と１４の求め方を図示しただけで、４５×５とか１６×１４とかを図の中に表したわけではありませんでした。 ４５×５と１６×１４を図に示すとしたら、＃２の補足欄に書かれているようにａ＝３という考え方を使うことにして、 ４５×１５と１６×４２を図示します。 ＃２の上の図の右下の１３×３の部分は、 １３×３－１２×３＝３ ＃２の上の図の右側の１３×１６の部分と、下の図の右側の１２×１５の部分とを、たすきがけで差を求めると、 １３×１５－１６×１２＝１３×（３＋１２）－（３＋１３）×１２＝１３×３－１２×３＝３ さらに全体で見て、４５×１６と、４２×１５とを、たすきがけで差を求めると、 ４５×１５－１６×４２＝（１６×２＋１３）×１５－１６×（１５×２＋１２）＝１３×１５－１６×１２＝３ というように、差が常に３になります。 これを図で表すと添付図のようになります。 上の図と下の図の除かれる部分を見ると、右下の１×３の部分以外は、正方形の上部か側部かの違いだけなので大きさは同じです。 よって、除かれる部分の差は３になります。
補足
何度も回答ありがとうございます。 作図によって、x,yを求める方法を示していただいたということなんですね。 よろしければ、もう少し質問させていただきたいのですが 作図の方法によってx,yが求められるのは何故なのでしょうか? a=3を使わずに、作図によって求められたものがx,yであると分かる方法はあるのですか?
- nag0720
- ベストアンサー率58% (1093/1860)
＃２です。 ＃２の添付図の上の図と下の図は、位置関係が同じであることが重要であって、大きさを較べることは無意味です。 下の図は、分かりやすいように上の図と同じような大きさで描きましたが、最小の正方形を１×１、全体の大きさを５×１４として描いても同じことです。 なので、４５×５a－１６×１４a＝a とか、a＝３とかという問題ではありません。 単純に、４５×５－１６×１４＝１ という意味です。 ＞また、上の図から、下の図を描くのには ＞やはり代数的な方法を使わないといけないのでしょうか? 図を描けば計算しなくてもｘとｙが求められます。 代数的に計算をするとしたら下記のようになります。 ４５と１６を互除法で最大公約数を求めると、 ４５－１６×２＝１３ １６－１３×１＝３ １３－３×４＝１ ３－１×３＝０ という式になります（最大公約数は１）。 上記の式から、２，１，４，３という正方形の数の数列が出てきますが、最後の３を除いて、２，１，４の数列を使って互除法の逆の計算をすれば、 ０＋４×１＝４ １＋１×４＝５ ４＋２×５＝１４ という方法で、５と１４が求められます。 （５と１４のどちらがマイナスになるかは、互除法の計算回数の偶奇で決まります）
補足
すみません。よくわからないです。 どの部分が４５×５で どの部分が１６×１４で どの部分が１なのでしょうか? 回答後半部分の代数的な方法は知っておりますが 「図を描けば計算しなくてもｘとｙが求められます」ですが 計算無しにどうやって縦が5で、横が14だと求められるのですか? 下の図は上の図から1×1の正方形を3個除いた以外に 81個の升目が除かれているように思いますが。 どちらがマイナスになるか関しては仰る見解で結構です。
- nag0720
- ベストアンサー率58% (1093/1860)
添付図の上の図は、A=16,B=45の場合の互除法のイメージです。 下の図は、上の図の最小の正方形を除いて、同じ配置で正方形を並べた図です。 下の図の最小の正方形の大きさを１×１とすると、全体の大きさは、５×１４になります。 これは、 ４５×５－１６×１４＝１ を意味しています。
補足
回答ありがとうございます。 下の図での1目盛りは、上の図でのa目盛り分として(今回はa=3) ４５×５a－１６×１４a＝a というイメージでよろしいしょうか? 左辺は理解できたのですが それが右辺と等しいことがわかるのに それぞれの図の食み出た部分を数えてしまったのですが (下の図の3×15から、上の図の1×42を引いた) それ以外に一発で3とわかる方法はありますか? また、上の図から、下の図を描くのには やはり代数的な方法を使わないといけないのでしょうか?
- saxan
- ベストアンサー率61% (8/13)
最後のご質問は 「ラメの定理(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が十分に大きい時の話でしょうから、定数項はあまり関係無いのでしょうが…。)
関連するQ&A
- {ax+by|x,y∈Z}
aとbが互いに素とは限らないときは、{ax+by|x,y∈Z}は、aとbの最大公約数の倍数全体の集合になる。この定理の証明でわからない点があるので質問します。 これらの定理は、S={ax+by|x,y∈Z}とおくと集合Sが"差に関して閉じている"という性質をもつ。 (x_1,x_2,y_1,y_2∈Zのとき、(ax_1+by_1)-(ax_2+by_2)=a(x_1-x_2)+b(y_1-y_2)ここでx_1-x_2,y_1-y_2∈Zとなること)ので、ある正の整数dを用いてS={nd|n∈Z}(Sはdの倍数全体)と表されるのであるが、 Sの最初の定義から、a∈S(x=1,y=0とする)かつb∈S(x=0,y=1とする)であるから、aとbはdの倍数(dはa,bの公約数)であり、・・・(1) ここからがわからないところです。他方、ax_0+by_0=dとなる整数x_0,y_0が存在するのだから、a,bの任意の公約数はdの約数であるから・・・(2)、dはa,bの最大公約数というわけである。で証明は終わるのですが、 証明の大まかな流れは、(1)よりd≦(a,b) (a,b)は、aとｂの最大公約数、(2)よりd≧(a,b)よって、d=(a,b)だと思うのですが、ax_0+by_0=dをa'dx_0+b'dy_0=dとしてみたりしても、a,bの任意の公約数はdの約数であるから、というのがわかりません。どなたか、他方、ax_0+by_0=dとなる整数x_0,y_0が存在するのだから、a,bの任意の公約数はdの約数である。を説明してください。お願いします。
- ベストアンサー
- 数学・算数
- ax+by+c=0とy=ax+bについて
質問の方、失礼致します。 ある参考書には、直線y=2x-3をax+by+c=0の形に2*x-1*y-3のように式変換をすればax+by+c=0の形でも直線y=2x-3を表すことが出来ると書いてあるのですが、2*x-1*y-3この式の -1 いわば ax+by+c=0 の b に当たる部分はどこからやってきたのでしょうか…？ 今現在の自分の理解が追いついていると思われる点は、ax+by+c=0 こちらの式の aは傾き xはx座標 yはy座標 cはy切片(xが0の時のyの位置) b…？ といった様な解釈になります。ご教示の程よろしくお願い致します。
- 締切済み
- 数学・算数
- Euclidの拡張互除法
Euclidの拡張互除法 互いに素な自然数A,Bがあるとき、Ax+By=1を満たす整数(x,y)が存在しますね。 また、この式からAB-BA=0をn倍して辺々引くと A(x-nB)+B(y+nA)=1 が成り立つので (x-nB,y+nA)も、Ax+By=1の整数解であると言えます。 これ以外に、Ax+By=1を満たす整数解は存在することはありますか? それと、Euclidの拡張互除法で Ax+By=1を満たす整数(x,y)を求めることができますが 無限に存在する(x,y)の組のうち、求まるのは 最も簡単なもののような気がしますが、それは正しいですか? 「最も簡単」というのは適当な表現が見つからないのですが 絶対値が一番小さい数の組み合わせといいますか 既約分数のようなイメージです。
- ベストアンサー
- 数学・算数
- 拡張ユークリッドの互除法のaとbは1組のみ？
例えば、下記URLを見ると、 http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ExEuclid.html -- x, yを0でない自然数とし，c=GCD(x,y)とする。このとき， ax+by=c となる整数a,bが存在する。そして，この a,b は実際に計算することが出来る。 -- のように拡張ユークリッドの互除法が解説されていますが、この時、a,bの組は1組なのでしょうか？それとも複数ある（可能性がある）うちの1組を特定できる、ということなのでしょうか？
- ベストアンサー
- 数学・算数
- ax + by (a,bは自然数で互いに素、x,yは自然数)
a,bは自然数で互いに素であるとき， ax + by (x,yは自然数) の形で表せない自然数の個数は いくつになるのでしょうか？ x,yを0以上の整数に変更するとどうなるのでしょうか？
- ベストアンサー
- 数学・算数
- 非負整数a,b,c,x,yで、ax+byとcが互いに素でなくなるのは?
非負整数a,b,c,x,yで、ax+byとcが互いに素でなくなるのは? a,b,cは互いに素でa^2+b^2=c^2、またx,y,cも互いに素であるとします。 例えば、(a,b,c)=(3,4,5)、(x,y)=(-1,7)ならば、 ax+by=25となって、cと素でなくなりますが、 どういった条件が成り立てば良いのでしょうか? 任意の整数の組(x,y)が与えられた時に、 (ax+by)/c≠0が約分できるような(a,b,c)の組を知りたいのです。 よろしくお願いします。 ちなみに以前の質問↓の続きです。 http://okwave.jp/qa/q6158436.html
- ベストアンサー
- 数学・算数
- ユークリッドの互除法
二つの整数a,bの最大公約数dを、ユークリッドの互除法で求める方法は分かります。 そうして求めたdは、適当な数x,yを使い、d=ax+byで表せることも何とか分かります。 しかし、d=ax+byが与えられたとき、ユークリッドの互除法を使って、特殊解xとyをどうやって求めたらよいのかが分かりません。 これまでの書き込みを見ても理解ができませんでした。 どなたか分かりやすくお教えください。
- ベストアンサー
- 数学・算数
- x＋y＋z＝５、3x＋y-15
x＋y＋z＝５、3x＋y-15を満たす任意のx、y、zに対して常にax²＋ｂy²＋ｃｚ²＝５²が成り立っている時定数a、ｂ、cを求めよ。 このときの、途中まではわかりますが x＋y＋z＝5・・・・・・(1) 3x＋y－z＝－15・・・(2) (1)＋(2) 4x+2y=-10 y=-2x-5・・・・(3) (3)を(1)に代入 x-2x-5+z=5 z=x+10・・・・・(4) ax＾2＋by＾2＋cz＾2＝5＾2 (3)、(4)を代入する ax＾2＋b（-2x-5）＾2＋c（x+10）＾2＝5＾2 ax＾2＋b（４x＾２＋２０ｘ＋２5）＋c（x＾２＋２０ｘ+100）－２５＝０ (a+4b+c)x＾2＋20(b+c)x+25b＋100c－２５＝０ ここまで、 このときに、解説には a+4b+c=0 a+3b=0 4a+9b-1=0 としているのですが なぜ０なんですか。何と係数比較しているんですか
- ベストアンサー
- 数学・算数
- y=ax^2-1 y=-b^2+1 が直交するとき（a>0,b>0)
y=ax^2-1 y=-b^2+1 が直交するとき（a>0,b>0) (1)a^2+b^2の最小値は？(2)2つのグラフで囲まれた面積の最大値は？ という問題で 直交条件より、8ab=a+bという式はでてきたのですがそこからわかりません。 お願いします
- 締切済み
- 数学・算数
お礼
ありがとうございました。 理解力が無くてすみません。