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ベストアンサー
- 回答日時:
>作図の方法によってx,yが求められるのは何故なのでしょうか?
#3の補足に、「回答後半部分の代数的な方法は知っておりますが」とありましたので、
0+4×1=4
1+1×4=5
4+2×5=14
という方法で、5と14が求められるのは知っているということですよね。
この計算式を図で表現しただけです。
>a=3を使わずに、作図によって求められたものがx,yであると分かる方法はあるのですか?
上記の方法を知っているのなら、a=3が関係ないことは分かっているのでは?
No.4
- 回答日時:
#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になります。
この回答への補足
何度も回答ありがとうございます。
作図によって、x,yを求める方法を示していただいたということなんですね。
よろしければ、もう少し質問させていただきたいのですが
作図の方法によってx,yが求められるのは何故なのでしょうか?
a=3を使わずに、作図によって求められたものがx,yであると分かる方法はあるのですか?
No.3
- 回答日時:
#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個の升目が除かれているように思いますが。
どちらがマイナスになるか関しては仰る見解で結構です。
No.2
- 回答日時:
添付図の上の図は、A=16,B=45の場合の互除法のイメージです。
下の図は、上の図の最小の正方形を除いて、同じ配置で正方形を並べた図です。
下の図の最小の正方形の大きさを1×1とすると、全体の大きさは、5×14になります。
これは、
45×5-16×14=1
を意味しています。
この回答への補足
回答ありがとうございます。
下の図での1目盛りは、上の図でのa目盛り分として(今回はa=3)
45×5a-16×14a=a
というイメージでよろしいしょうか?
左辺は理解できたのですが
それが右辺と等しいことがわかるのに
それぞれの図の食み出た部分を数えてしまったのですが
(下の図の3×15から、上の図の1×42を引いた)
それ以外に一発で3とわかる方法はありますか?
また、上の図から、下の図を描くのには
やはり代数的な方法を使わないといけないのでしょうか?
No.1
- 回答日時:
最後のご質問は
「ラメの定理(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が十分に大きい時の話でしょうから、定数項はあまり関係無いのでしょうが…。)
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 写真は「ユークリッドの互除法」のイメージ図なのですが これで何故17が最大公約数になるのか分かりませ 2 2023/03/05 16:54
- 数学 再質問 写真は「ユークリッドの互除法」のイメージ図なのですが これで何故17が最大公約数になるのか分 4 2023/03/05 17:08
- 数学 黄色マーカーの意味がよく分かりません。 X軸方向に4倍、Y軸方向に8倍に引き伸ばした らへんは何とな 3 2023/04/10 20:08
- 大学受験 整数問題 Nを正の整数とする。 N+18がN+2の倍数となるようなNの値の個数を求めたい。 解説に、 1 2022/08/13 12:25
- C言語・C++・C# C#の問題で2つの整数a,bの最大公約数(GCD)を求めるユークリッドの互除法は,aをbで割った余り 2 2022/06/26 16:52
- 数学 中一数学の【最大公約数と最小公倍数】の問題です。 1問だけでも教えていただけると嬉しいです。 (1) 4 2022/08/01 10:19
- 数学 難題集から 最大と最小 7 2023/02/22 19:36
- 数学 ユークリッドの互除法、合同式の問題について 1 2022/05/08 11:49
- 数学 最小公倍数と最大公約数の求め方で画像のような計算法があったのですが、理解できません。 なぜ2つ数24 4 2022/04/10 13:37
- その他(プログラミング・Web制作) PythonでLoopを使って配列内の文字列を結合する。そして [] を削除する 1 2022/03/31 23:28
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
平方ミリメートルを平方メート...
-
平方メートルをメートルに直し...
-
縮小率の計算方法を教えてください
-
面積から縦横の長さを求めたい
-
200平米って、200m×200mの正方...
-
平方cm指定の印刷面積について
-
ルートって何のためにあるの?
-
「平方メートル」と「メートル...
-
広さについて
-
重心の求め方を教えてください
-
格子点上に出来る正方形の数
-
正方形に円が重なる面積の問題...
-
【こたつ、正方形か長方形かど...
-
四角形ABCDにおいて、 ∠A=∠B=∠C...
-
数学の図形の面積についてです...
-
隙間がない図形パターン
-
変形図形の重心点(中心点)の...
-
1万メートル四方と書かれている...
-
数学の問題です。 写真の斜線部...
-
円と球の内部の格子点について
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
平方ミリメートルを平方メート...
-
平方メートルをメートルに直し...
-
縮小率の計算方法を教えてください
-
ルートって何のためにあるの?
-
正方形を表現する関数はありま...
-
この八角形を分度器と、コンパ...
-
面積から縦横の長さを求めたい
-
確率の問題です。ご教授いただ...
-
小学生での図形
-
20m2って縦何メートルで横何...
-
正方形は長方形ですか?
-
広さについて
-
「平方メートル」と「メートル...
-
200平米って、200m×200mの正方...
-
正方形に円が重なる面積の問題...
-
対角線の長さが分かっている場...
-
面積5平方センチメートルの正...
-
数学の図形の面積についてです...
-
√は生活のどんな場面ででてくる...
-
13平方センチメートルの正方...
おすすめ情報