- 締切済み
整数
- みんなの回答 （2）
- 専門家の回答
みんなの回答
ユークリッドの互除法の正当性については理解されているものとします。以下ではx,yを具体的に求めてみます。厳密な証明は他の回答者の回答等を参考にしてください。 a=329,b=218 とする。互除法でa,bの最大公約数を求める。 329=218(1)+111 218=111(1)+ 107 111=107(1)+ 4 107=4(26)+ 3 4=3(1)+ 1 3=1(3)+ 0 (a,b)=1 上のプロセスを逆にたどる。 1 =4-3 =4-(107-4(26)) =4(27)-107 =(111-107)(27)-107 =111(27)-107(28) =111(27)-(218-111)(28) =111(55)-218(28) =(329-218)(55)-218(28) =329(55)-218(83) =329(55)+218(-83) x=55,y=-83 上を見ればわかると思いますが補足すると、互除法の各ステップが q0=q1(x0)+q2 q1=q2(x1)+q3 ： ： のようになっているので、例えばq3ならq3をq2とq1で表せるし、q2をq1とq0で表せるのでq3をq0とq1の整数倍の和で表わせるということです。
- arrysthmia
- ベストアンサー率38% (442/1154)
つい先日。これと同一の質問に答えたばかり。 http://oshiete1.goo.ne.jp/qa5280904.html
関連するQ&A
- 整数について
a,bは整数とする (a,b)=1の時 ax+by=1を満たす整数x,yが存在することを示せ で次のように証明してみました。 (1)(a,b)=dの時、ax+by=dを満たす整数x,yが存在するという定理を用 いて考えてみる。 (a,b)=dだからユークリッドの互助法を使ってゆくと最後はdで割り 切れる。計算が次のようになったとする。 a=bq_1+r_1 従ってr_1=a-bq_1・・・(1) b=r_1q_2+r_2 従ってr_2=b-r_1q_2・・・(2) r_1=r_2q_3+r_3 従ってr_3=r1-r_2q_3・・・(3) r_2=r_3q_4+0 (r_3=d) ここで(3)に(2)を代入 d=r_3=r_1-(b-r_1q_2)q_3 =r_1-bq_3+r_1q_2q_3 =r_1(1+q_2q_3)-bq_3・・・(4) (4)のr_1へ(1)を代入 d=(a-bq_1)(1+q_2q_3)-bq_3 =a+aq_2q_3-bq_1-bq_1q_2q_3-bq_3 =a(1+q_2q_3)+(-q_1-q_1q_2q_3-q_3)b (1+q_2q_3)=x , (-q_1-q_1q_2q_3-q_3)=yとおくと d=xa+by 従って(a,b)=ax+by よって(a,b)=1の時にax+by=1となる整数x,yが存在する。 このように証明しました。大丈夫でしょうか？ (2)また、次の定理を使った場合はどう証明しますか。 定理・・自然数a,b(a>b)についてaをbで割りその整商をq、余りをr とするとa=bq+r (0≦r<b) このとき(a,b)=(b,r) この定理を使った場合の証明はなりますか。 よろしくお願いしま す。
- 締切済み
- 数学・算数
- ユークリッドの互除法
二つの整数a,bの最大公約数dを、ユークリッドの互除法で求める方法は分かります。 そうして求めたdは、適当な数x,yを使い、d=ax+byで表せることも何とか分かります。 しかし、d=ax+byが与えられたとき、ユークリッドの互除法を使って、特殊解xとyをどうやって求めたらよいのかが分かりません。 これまでの書き込みを見ても理解ができませんでした。 どなたか分かりやすくお教えください。
- ベストアンサー
- 数学・算数
- 証明について
a,bを整数とするとき次の2つの条件(i),(ii)について(i)と(ii)は同値であることを証明する問題です。 (i) a,bはお互いに素である。すなわち、aとｂの最大公約数は1である。 (ii) ax(0)+by(0)=1となる２つの整数x(0),y(0)が存在する。 (i)の問題について ２つの整数aとbの最大公約数をGとおくと a=a'G,b=b'G(a',b'はお互いに素）とする。 (1)aをbで割ったときの商をq,余りをrとするとa=bq+r rについて解くと r=a-bq 2つの整数はaとbはa=a'G,b=b'G(a',b'とおけるので r=a'G-b'G この後どのように証明するのでしょうか？ (ii) ax(0)+by(0)=1となる２つの整数x(0),y(0)が存在はどのように証明するのでしょうか？
- 締切済み
- 数学・算数
- ユークリッドの互除法
ユークリッドの互除法の処方でつまづいています。 どなたか教えて頂けませんか。 aとbは正の整数でb≦aの関係にある。 aとbの最大公約数gcd(a,b)。 この時gcd(a,b)=ax+byの解となる(x,y)のペアはいくついるのでしょうか? 直感ですと(x,y)は一つしか存在しないように感じるのですが、どうやって記述すればいいのでしょうか？ よろしくお願いします。
- ベストアンサー
- 数学・算数
- 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あまりをrとすると a=bq+r であるので r=a-bq である。ここで、この右辺はa bの最大公約数でわり切れるのは、なぜか教えて下さい。あと a bの最大公約数がrとb の公約数でもあるのはなぜですか？お願いします。
- ベストアンサー
- 数学・算数
- {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 にたいして，m = 11a + b，n = 3a + b とおく．つぎのことを証明せよ． m，n の最大公約数は，a，b の最大公約数をd として，2d，4d，8d のいずれかである． 僕はユークリッドの互除法を考えました。 (11a+b)=(3a+b)*1+8a よってmnの最大公約数は3a+bと8aの最大公約数である。 さらに(3a+b)=(3/8)*8a+b として8aとbの最大公約数が求める最大公約数と考えましたが、ここで矛盾が生じます。 bは奇数であるので偶数の2d等を因数に持たない。 よく考え直してみたのですが、ユークリッドは商が整数にならなければならないのでしょうか？2回目にユークリッドを使うときに商が3/8となってるのがまずいのでしょうか？ またこの問題はどう解いたらよいでしょうか？教えてください。
- 締切済み
- 数学・算数
お礼
ありがとうございます。