ユークリッドの互除法の証明方法
- ユークリッドの互除法の証明方法を教えてください。
- ユークリッドの互除法はgcd(a,b)=ax+byとなる整数(x,y)を持つことを証明できます。
- 帰納法を使って、n=k、n=k+1の時にもユークリッドの互除法が成り立つことを示せます。
- ベストアンサー
ユークリッドの互除法の証明
ユークリッドの互除法なんですが、これを使った証明がわからないので質問させてください。 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の時にどうすればうまく証明できるのかわかりません。 どなたか教えて下さい。
- koni-ami
- お礼率14% (22/147)
- 数学・算数
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
n＝２ のとき a=bq1+r2 b=r2q2 で 、 a*1-bq1=r2=gcd(a,b) ----------------- n＝3 のとき A=Bq1+r2 -------- B=r2q2+r3 r2=r3q3 で a=B , b=r2 として成り立つから Bx+r2y=r3 gcd(A,B)=r3=Bx+r2y=Bx+(A-Bq1)y=Ay+B(x-q1y)
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
日本語がおかしいことに気付いていますか?
関連するQ&A
- ユークリッドの互除法
ユークリッドの互除法の処方でつまづいています。 どなたか教えて頂けませんか。 aとbは正の整数でb≦aの関係にある。 aとbの最大公約数gcd(a,b)。 この時gcd(a,b)=ax+byの解となる(x,y)のペアはいくついるのでしょうか? 直感ですと(x,y)は一つしか存在しないように感じるのですが、どうやって記述すればいいのでしょうか？ よろしくお願いします。
- ベストアンサー
- 数学・算数
- ユークリッドの互除法
ユークリッドの互除法を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
- ユークリッドの互除法
ユークリッドの互除法がよくわかりません。 m>nとして(m=nならばm=gcd(m,n)) m=sn+t (n>t)とあらわせる。 ここでgcd(m,n)=gcd(n,t)となるのがわかりません。 これがわかったらあとはあまり部分が０になるまでやればそのときに最大公約数が出るというのはわかるのですが、、、
- ベストアンサー
- 数学・算数
- ユークリッドの互除法
すべての自然数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) といったかんじで大まかには合ってますか？ 間違いがありましたらご指摘ください よろしくお願いします
- ベストアンサー
- 数学・算数
- ユークリッドの互除法について
質問させて頂きます。 （有理整数環Ｚにωを添付した整域Z[ω]をＲとする。Ｒ=Z[ω]={a+bω}において） ω=(-1+√3i)/2 とした場合、α=16+14ω、β=11+9ω の最大公約元、最小公倍元の求め方をユークリッド互除法にて教えて下さい。 よろしくお願いいたします。
- 締切済み
- 数学・算数
- ユークリッドの互除法について
こんにちは。高校数学A、ユークリッドの互除法についてです。 問題集の 整数aを正の整数bで割った余りをrとする。aとbの最大公約数はbとrの最大公約数と一致することを証明せよ。 という問題の解説で aをbで割った商をqとすると a=bq+r aとbの最大公約数をg1、bとrの最大公約数をg2とし、 a=a'g1,b=b'g1：b=b”g2,r=r'とする。 ただし、a',b',b”,r'は整数で、a'とb',b”とr'はそれぞれ互いに素である。このとき、 r=a－bq=a'g1－b'g1q=(a'－b'q)g1 a'－b'rは整数であるから、g1はrの約数、★すなわちbとrの公約数になる。 ★よってg1≦g2 以下略 この★の部分がわかりません。 g1がrの約数になると bとrの公約数とも言える理由は何なのでしょうか？ そしてなぜg1よりg2のほうが大きくなるのでしょうか？ どなたかよろしければ ご教授お願い致します。
- 締切済み
- 数学・算数
- ユークリッドの互除法
二つの整数a,bの最大公約数dを、ユークリッドの互除法で求める方法は分かります。 そうして求めたdは、適当な数x,yを使い、d=ax+byで表せることも何とか分かります。 しかし、d=ax+byが与えられたとき、ユークリッドの互除法を使って、特殊解xとyをどうやって求めたらよいのかが分かりません。 これまでの書き込みを見ても理解ができませんでした。 どなたか分かりやすくお教えください。
- ベストアンサー
- 数学・算数
- ユークリッドの互除法
ユークリッドの互除法の証明の一部なのですが aをで割った商をbあまりをrとすると a=bq+r であるので r=a-bq である。ここで、この右辺はa bの最大公約数でわり切れるのは、なぜか教えて下さい。あと a bの最大公約数がrとb の公約数でもあるのはなぜですか？お願いします。
- ベストアンサー
- 数学・算数
- ユークリッドの互除法についての問題です。
ユークリッドの互除法についての問題です。 a,bが任意の整数のとき、次の式を満たす整数xは必ずあるか。 (1)aが5の倍数でないとき ax≡b (mod5) (2)aが4の倍数でないとき ax≡b (mod4) 誰か教えてください。
- ベストアンサー
- 数学・算数
補足
元が英語で書かれた問題なんです＞＜；