- ベストアンサー
拡張ユークリッドの互除法の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組を特定できる、ということなのでしょうか？
- netw2009
- お礼率27% (176/650)
- 数学・算数
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
いくらでもありますよ。 x=cm,y=cn(m,nは互いに素)と表せます。 この式をax+by=cに代入すると acm+bcn=c am=1-bn ここでa1.b1がこの式を満たすとするとb=b1+km(k:整数)を右辺に入れると 1-(b1+km)n=1-b1*n-kmn=a1*m-kmn=(a1-kn)m となり、(a,b)=(a1-kn,b1+km)もこの式を満たすことになります。
関連するQ&A
- ユークリッドの互除法
ユークリッドの互除法の処方でつまづいています。 どなたか教えて頂けませんか。 aとbは正の整数でb≦aの関係にある。 aとbの最大公約数gcd(a,b)。 この時gcd(a,b)=ax+byの解となる(x,y)のペアはいくついるのでしょうか? 直感ですと(x,y)は一つしか存在しないように感じるのですが、どうやって記述すればいいのでしょうか？ よろしくお願いします。
- ベストアンサー
- 数学・算数
- ユークリッドの互除法
二つの整数a,bの最大公約数dを、ユークリッドの互除法で求める方法は分かります。 そうして求めたdは、適当な数x,yを使い、d=ax+byで表せることも何とか分かります。 しかし、d=ax+byが与えられたとき、ユークリッドの互除法を使って、特殊解xとyをどうやって求めたらよいのかが分かりません。 これまでの書き込みを見ても理解ができませんでした。 どなたか分かりやすくお教えください。
- ベストアンサー
- 数学・算数
- ユークリッドの互除法についての問題です。
ユークリッドの互除法についての問題です。 a,bが任意の整数のとき、次の式を満たす整数xは必ずあるか。 (1)aが5の倍数でないとき ax≡b (mod5) (2)aが4の倍数でないとき ax≡b (mod4) 誰か教えてください。
- ベストアンサー
- 数学・算数
- 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は正の整数で、b≦aである。 r_0=a、r_1=bとしq_iとr_iは整数で0<r_i<r_(i-1)である。(qについては特に指示はありません) このとき r_0=r_1*q_1+r_2 r_1=r_2*q_2+r_3 ・ ・ ・と続き r_(n-2)=r_(n-1)*q_(n-1)+r_n r_(n-1)=r_n*q_n が成り立つ。 n≧2の時、ユークリッドの互除法はgcd(a,b)=ax+byとなる整数(x,y)を持つことを証明しなさい。 これは帰納法を使えばいいのでしょうか？ n=2の時にr_2=r_0-r_1*q_1が成り立つことはr_(n-1)=r_n*q_n にn=2を代入して示せるのですがn=k、n=k+1の時にどうすればうまく証明できるのかわかりません。 どなたか教えて下さい。
- ベストアンサー
- 数学・算数
- ユークリッドの互除法
ユークリッドの互除法をJavascriptで書こうとしてます。以下のように書いたのですが、うまく動きません。(45と60の最大公約数を求めるプログラム) <script> window.alert(gcd(45, 60)); function gcd(a, b){ var r=a%b; if(r==0){ return b; }else{ gcd(b, r); } } </script> undifinedとなってしまいます。どうしたら正確な答えが出るでしょうか？
- ベストアンサー
- JavaScript
- 一次合同式の解き方
３ｘ≡６（mod９）のｘを求めよという問題でgcd（3，9）= 3より6は3の倍数であるので解を持つことは分かるのですが，ｘを具体的に求めることができません．参考にしたサイトは ttp://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ExEuclid.html「ここの拡張ユークリッド互除法の応用例２」の部分です． 拡張ユークリッドの互除法を用いても 3*1+9*0=3より3*1=3 mod 9 と当然の結果しか得られず進むことができません． ｘをどのようにすれば求めることができますか？手計算で表を書けば出来るという話ではなく参考サイトのように数学らしい（？）の解き方でお願いします．
- ベストアンサー
- 数学・算数
- 拡張ユークリッドについて
ax+by=gcd(a,b)でx, yを求める際にa, bのどちらかがもしマイナスの場合成り立つのでしょうか？サイトによっては正の整数と書いてるサイトもあれば，整数と書いてるサイトもあるので・・・・ウィキは嘘ばかり書いてることが多いと聞いたことがるのでどうも信用できません．．． 実際のところ成り立つのでしょうか？
- 締切済み
- 数学・算数
お礼
回答ありがとうございます。