- 締切済み
拡張ユークリッドについて
- みんなの回答 （4）
- 専門家の回答
みんなの回答
- 33550336
- ベストアンサー率40% (22/55)
拡張ユークリッドという言葉は聞いたことがありませんが、正の整数でできるのならば負の整数でもできるのでは？ a、bが正の整数で ax+by=gcd(a,b) が成立しているならa,bが負の整数の場合、axを(-a)(-x)にかえたりbyを(-b)(-y)にかえたりすればよいのでは、と単純に考えたわけですが… それにそもそもその式は (a)+(b)=(a,b)=(gcd(a,b)) からきている式です。（(a)はaによって生成される単項イデアル） 整数環はPIDであることからgcd(a,b)の存在が保証される訳ですが、 正か負か、の差は生成元のとり方の違いだけなので、本質的にはかわらないと思います。
>ax+by=gcd(a,b)でx, yを求める際にa, bのどちらかがもしマイナスの場合成り立つのでしょうか？ gcd(a,b) = c として、ax+by = c の一つの解を (Xo, Yo) としましょう。 任意の整数 K に対し、 X = Xo + K*b Y = Yo - K*a も ax+by = c を満足しますね。 つまり、a, b のどちらかがマイナスの場合も成り立つ。
- koko_u_u
- ベストアンサー率18% (216/1139)
>実際のところ成り立つのでしょうか？ 「拡張ユークリッド」という言い回しもあんまり聞かないけど、 その証明をトレースすれば a, b に対する前提条件が整数でも成立するか容易にわかると思います。
- Tacosan
- ベストアンサー率23% (3656/15482)
a, b のどちらかがマイナスのときに「何が」成り立つかどうか質問されているのでょうか?
関連するQ&A
- ユークリッドの互除法
ユークリッドの互除法の処方でつまづいています。 どなたか教えて頂けませんか。 aとbは正の整数でb≦aの関係にある。 aとbの最大公約数gcd(a,b)。 この時gcd(a,b)=ax+byの解となる(x,y)のペアはいくついるのでしょうか? 直感ですと(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の最大公約数dを、ユークリッドの互除法で求める方法は分かります。 そうして求めたdは、適当な数x,yを使い、d=ax+byで表せることも何とか分かります。 しかし、d=ax+byが与えられたとき、ユークリッドの互除法を使って、特殊解xとyをどうやって求めたらよいのかが分かりません。 これまでの書き込みを見ても理解ができませんでした。 どなたか分かりやすくお教えください。
- ベストアンサー
- 数学・算数
- 拡張ユークリッド互除法による乗法逆元の求め方
こんにちは。 タイトルの通りの質問なのですが、過去ログを参考にしても特別分からないところがあったため、質問させて下さい。 11^-1 ≡ x(mod 31) このxを求めたいのですが、11x * 31y = gcd(11, 31)として解いたら、 -14 * 11 + 5 * 31 = 1 となってしまい、うまくいきません。 以下、自分なりの解法です。 ----------------------------------------------------- 11^-1 ≡ x(mod 31)より、11x ≡ 1(mod31) これは、11x + 31y = 1を示す。 gcd(11, 31) 11 = a, 31 = b とする = gcd(31, 11) → b = 2a + 9 → 9 = -2a + b = gcd(11, 9) → a = (-2a + b) + 2 → 2 = 3a - b = gcd(9, 2) → -2a + b = 4(3a - b) + 1 ―(1) = gcd(2, 1) = gcd(1, 0) = 1 (1)の式より、-14a + 5b = 1 先ほどの式と照らし合わせて、(x, y) = (-14, 5) したがって、11^-1 ≡ -14(mod 31) ----------------------------------------------------- おそらく、11x > 31yの条件が取り入れられてないのが原因だと思いますが、どう使えばいいかわからないです。 どなたか正しい解法を教えてください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 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の時にどうすればうまく証明できるのかわかりません。 どなたか教えて下さい。
- ベストアンサー
- 数学・算数
- {ax+by|x,y∈Z}
aとbが互いに素とは限らないときは、{ax+by|x,y∈Z}は、aとbの最大公約数の倍数全体の集合になる。この定理の証明でわからない点があるので質問します。 これらの定理は、S={ax+by|x,y∈Z}とおくと集合Sが"差に関して閉じている"という性質をもつ。 (x_1,x_2,y_1,y_2∈Zのとき、(ax_1+by_1)-(ax_2+by_2)=a(x_1-x_2)+b(y_1-y_2)ここでx_1-x_2,y_1-y_2∈Zとなること)ので、ある正の整数dを用いてS={nd|n∈Z}(Sはdの倍数全体)と表されるのであるが、 Sの最初の定義から、a∈S(x=1,y=0とする)かつb∈S(x=0,y=1とする)であるから、aとbはdの倍数(dはa,bの公約数)であり、・・・(1) ここからがわからないところです。他方、ax_0+by_0=dとなる整数x_0,y_0が存在するのだから、a,bの任意の公約数はdの約数であるから・・・(2)、dはa,bの最大公約数というわけである。で証明は終わるのですが、 証明の大まかな流れは、(1)よりd≦(a,b) (a,b)は、aとｂの最大公約数、(2)よりd≧(a,b)よって、d=(a,b)だと思うのですが、ax_0+by_0=dをa'dx_0+b'dy_0=dとしてみたりしても、a,bの任意の公約数はdの約数であるから、というのがわかりません。どなたか、他方、ax_0+by_0=dとなる整数x_0,y_0が存在するのだから、a,bの任意の公約数はdの約数である。を説明してください。お願いします。
- ベストアンサー
- 数学・算数
- ユークリッドの互除法
すべての自然数a,bに対して sa+tb=gcd(a,b) となるような整数s,tがあることの証明問題なのですが、 a=bの場合はs=0, t=1で条件を満たす a<bとして一般性を失わない 数学的帰納法で 1) a+b=2 a=b=1なので s=0, t=1で条件を満たす 2)自然数kに対してa+b≦kで条件を満たすとき、 a+b=k+1のときは sa+t(b-a)=gcd(a,b-a) を満たす整数s,tが存在する(a+(b-a)≦kは明らか） sa+t(b-a)=gcd(a,b-a) sa+tb-ta=gcd(a,b-a) (s-t)a+tb=gcd(a,b) といったかんじで大まかには合ってますか？ 間違いがありましたらご指摘ください よろしくお願いします
- ベストアンサー
- 数学・算数
- ユークリッドの互除法についての問題です。
ユークリッドの互除法についての問題です。 a,bが任意の整数のとき、次の式を満たす整数xは必ずあるか。 (1)aが5の倍数でないとき ax≡b (mod5) (2)aが4の倍数でないとき ax≡b (mod4) 誰か教えてください。
- ベストアンサー
- 数学・算数
補足
x, yが拡張ユークリッドで正しくもとまる，ということです．