- 締切済み
ユークリッドの互除法を用いて解く問題がわかりません
2題あるのですが (1)299x+323y=1を満たす整数x、yの組を一組求める (2)(d・e)-1がaで割り切れるようなeを求める という問題です。 考えたのですが、答えを導出できませんでした。 導出過程と答えを教えてください。よろしくお願いします
- みんなの回答 (7)
- 専門家の回答
みんなの回答
- sinisorsa
- ベストアンサー率44% (76/170)
- sinisorsa
- ベストアンサー率44% (76/170)
- sinisorsa
- ベストアンサー率44% (76/170)
- mister_moonlight
- ベストアンサー率41% (502/1210)
- sinisorsa
- ベストアンサー率44% (76/170)
関連する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)は一つしか存在しないように感じるのですが、どうやって記述すればいいのでしょうか? よろしくお願いします。
- ベストアンサー
- 数学・算数
- 数学のユークリッド互除法についてです。
数学のユークリッド互除法についてです。 [4201x-3859y=1の1組の非負整数解を求めよ]の解答と解法を教えて下さい。 何度計算しても負の値になってしまいます。 よろしくお願いします。
- 締切済み
- 大学・短大
- 問題集の問題なんですが・・・
数学の問題集を解いていたのですが、答えの導出過程が分からないので、もしお解かりの方はどうか教えてください。 2直線 m : {x-1} = {(y-3)/a} = {(z+4)/(-3)} l : {x+2} = {(y+7)/2} = {(z+b)/3} が直交するようにa,bの値を定めよ。 って問題なんですが、aは単純に方向ベクトルの内積が0という関係を用いて、4が出たのですが、bの解答の導出過程がわかりません。 答えでは、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#
お礼
ありがとうございます でも、これでは(17・(-627))-1が2132で割り切れないのですが・・・ もしeに627を用いる場合は(17・(-627))+1が2132で割り切れそうです やはり627ではないのでしょうか?