- ベストアンサー
ユークリッドの互除法
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
Ｎｏ．１です 補足感謝ヾ（＠⌒ー⌒＠）ノ ＞aとbが互いに素ではない限り、(x,y)は無数にに存在するということですか？ そのとおり（児玉清さん風に）！ 数字を実際に入れてみれば、すぐに出ますよ＾＾； (=^. .^=) ｍ（＿ ＿）ｍ (=^. .^=) ｇｃｄ（ａ，ｂ）＝２ （ａ，ｂ）＝（４，２）とすると ２＝（４－２）＝（ａ－ｂ） ＝（８－６）＝（２ａ－３ｂ） ＝（１２－１０）＝（３ａ－５ｂ） ＝（１６－１４）＝（４ａ－７ｂ） 以下まだ無限にあります。
その他の回答 (2)
- rnakamra
- ベストアンサー率59% (761/1282)
x,yに何も条件はないのですか。 gcd(a,b)=ax+by を満たす(x,y)がひとつあり(x0,y0)とすると x=x0+bn,y=y-an (nは整数)とするとやはり上の式を満たします。 つまり、ひとつしかない、ということはありえません。ひとつの(x0,y0)の組から無限に作ることが可能です。
- B-juggler
- ベストアンサー率30% (488/1596)
えっと、こんばんは。 う～ん、一つだけしか存在しないのは ｛（ｘ、ｙ）が｝ ａ，ｂ が互いに素 ⇔ｇｃｄ（ａ，ｂ）＝１ のときだけですよ。 こういうのは例を挙げて考えてみれば、そんなに苦労はしません。 ａ＝１０、ｂ＝５ としましょうか？ ｇｃｄ（ａ，ｂ）＝５ ですね。 ５＝ ａ － ｂ ＝ ２ａ － ３ｂ ＝ ３ａ － ５ｂ・・・・・ これはキリがないですよ。 順に（ｘ、ｙ）＝（１、－１）、（２、－３）（３、－５）・・ ｇｃｄ（ａ，ｂ）＝１ のときは 互除法で ａ，ｂを崩していって、 この辺は多分やられていると思います。 例を挙げますので、これでできないときはまた言ってください。 ａ＝６５ ｂ＝１９ と取ったとき ｇｃｄ（ａ，ｂ）＝１です。 （ｘ、ｙ）＝ （－７、２４）じゃなかったかな？ (=^. .^=) ｍ（＿ ＿）ｍ (=^. .^=)
補足
aとbが互いに素ではない限り、(x,y)は無数にに存在するということですか？
関連するQ&A
- ユークリッドの互除法
二つの整数a,bの最大公約数dを、ユークリッドの互除法で求める方法は分かります。 そうして求めたdは、適当な数x,yを使い、d=ax+byで表せることも何とか分かります。 しかし、d=ax+byが与えられたとき、ユークリッドの互除法を使って、特殊解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組を特定できる、ということなのでしょうか？
- ベストアンサー
- 数学・算数
- ユークリッドの互除法についての問題です。
ユークリッドの互除法についての問題です。 a,bが任意の整数のとき、次の式を満たす整数xは必ずあるか。 (1)aが5の倍数でないとき ax≡b (mod5) (2)aが4の倍数でないとき ax≡b (mod4) 誰か教えてください。
- ベストアンサー
- 数学・算数
- ユークリッドの互除法
ユークリッドの互除法を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
- ユークリッドの互除法の証明
ユークリッドの互除法なんですが、これを使った証明がわからないので質問させてください。 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の時にどうすればうまく証明できるのかわかりません。 どなたか教えて下さい。
- ベストアンサー
- 数学・算数
- 数学のユークリッド互除法についてです。
数学のユークリッド互除法についてです。 [４２０１ｘ－３８５９ｙ=１の１組の非負整数解を求めよ]の解答と解法を教えて下さい。 何度計算しても負の値になってしまいます。 よろしくお願いします。
- 締切済み
- 大学・短大
- 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)の組のうち、求まるのは 最も簡単なもののような気がしますが、それは正しいですか? 「最も簡単」というのは適当な表現が見つからないのですが 絶対値が一番小さい数の組み合わせといいますか 既約分数のようなイメージです。
- ベストアンサー
- 数学・算数
- ユークリッドの互除法
ユークリッドの互除法がよくわかりません。 m>nとして(m=nならばm=gcd(m,n)) m=sn+t (n>t)とあらわせる。 ここでgcd(m,n)=gcd(n,t)となるのがわかりません。 これがわかったらあとはあまり部分が０になるまでやればそのときに最大公約数が出るというのはわかるのですが、、、
- ベストアンサー
- 数学・算数
補足
この問題の前の設問でrnakamraさんの書かれたことが問われていたので、やはり無限にあるのですね。 またx,yには条件はありません。 だとするとgcd(252,192)=252x+192yの(x,y)も無限個存在するのでしょうか?