- 締切済み
ユークリッドの互除法を用いて解く問題がわかりません
noname#101087の回答
>（１）299x＋323y＝1を満たす整数x、yの組を一組求める #1 さんの結果 ↓ xo = 148, yo = -137 念のため、非負解(x,y ともに)の有無を調べてみると「無し」でした。 一般解は、 xk = xo - 323*k, yk = yo + 299*k ですが、 x1 = -175, y1 = 162 非負解があるとすれば、xo, x1 の間。 つまり「無し」。 >（２）（d・e）-1 がaで割り切れるようなeを求める a, d が所与(整数)として不定方程式 d*x + a*y = 1 を考えれば、解 x が e を与える、ということかな。
関連するQ&A
- ユークリッドの互除法
二つの整数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) 誰か教えてください。
- ベストアンサー
- 数学・算数
- ユークリッドの互除法
ユークリッドの互除法の処方でつまづいています。 どなたか教えて頂けませんか。 aとbは正の整数でb≦aの関係にある。 aとbの最大公約数gcd(a,b)。 この時gcd(a,b)=ax+byの解となる(x,y)のペアはいくついるのでしょうか? 直感ですと(x,y)は一つしか存在しないように感じるのですが、どうやって記述すればいいのでしょうか？ よろしくお願いします。
- ベストアンサー
- 数学・算数
- 数学のユークリッド互除法についてです。
数学のユークリッド互除法についてです。 [４２０１ｘ－３８５９ｙ=１の１組の非負整数解を求めよ]の解答と解法を教えて下さい。 何度計算しても負の値になってしまいます。 よろしくお願いします。
- 締切済み
- 大学・短大
- 問題集の問題なんですが・・・
数学の問題集を解いていたのですが、答えの導出過程が分からないので、もしお解かりの方はどうか教えてください。 ２直線 m : {x-1} = {(y-3)/a} = {(z+4)/(-3)} l : {x+2} = {(y+7)/2} = {(z+b)/3} が直交するようにa,bの値を定めよ。 って問題なんですが、aは単純に方向ベクトルの内積が０という関係を用いて、４が出たのですが、ｂの解答の導出過程がわかりません。 答えでは、b=1 となっているのですが、どうすれば出るのでしょうか？ どうか教えてください。
- 締切済み
- 数学・算数
- ユークリッドの互除法について
波線部分のところで (x-8)は-17kの倍数という解き方で 答えをx=-17k+18にしましたが かいとうではx=17k+18となっています。 もう一方の答えも自分はy=30k-14にしましたが答えはy=-30k-14になっています。 どちらでも答えはあっていますか？
- ベストアンサー
- 数学・算数
- ユークリッドの互除法
(1)a,bは互いに素な整数である。 (2)a,bについて、1 = ra + sb が成立する(a,b,r,sは整数) この2命題の関係性を調べよ、という問題があります。 以下の回答は正しいでしょうか。 ディオファントゥスの定理(ベズーの等式)より、a,b二数の最大公約数をdとする時、整数r,.sを適切に取ると、d=ra+sb (ディオファントゥスの定理は別途証明することとします。具体的な証明はhttp://questionbox.jp.msn.com/qa7620419.htmlでしています) よって、d=1の時、(1)は(2)の必要十分条件である 上述の定理においては(1)と(2)が同義のため、一言で書いていますが、これで通用する書き方なのか疑問に思っています。
- ベストアンサー
- 数学・算数
- 拡張ユークリッドの互除法の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*e+b*Phi=1 となるようなa,bを求めるプログラムを作りたいのですが 以下のようにしても正しい値になりません どこが間違っているのでしょうか？ e=53499289; Phi=96298720; d=0; d_old=1; Psi=1; Psi_old=0; for (;Phi!=0;){ a= e/Phi; h=e; e=Phi; Phi= h%Phi; h=d_old; d_old=d; d=h-d*a; h=Psi_old; Psi_old=Psi; Psi=h-Psi*b; } if (e<0){ b=-e; }else{ b=e; } printf ("(%d)*e+(%d)*Phi_n=%d\n", d_old,Psi_old,b); 正しくは 9*e+(-5)*Phi=1 となるはずです
- ベストアンサー
- C・C++・C#
お礼
回答ありがとうございます。 自然数だけの解があるかどうかを確認してくださったわけですね （２）についてなんですが、完全にdとaを定義し忘れていました。 設問ではｄは17、aは2132となっていました