• 締切済み
  • 暇なときにでも

証明

a,bを整数とするときZ次の2つの条件(i),(ii)について(i)と(ii)は同値であることを証明する問題です。 (i) a,bはお互いに素である。すなわち、aとbの最大公約数は1である。 (ii) ax(0)+by(0)=1となる2つの整数x(0),y(0)が存在する。 という問題です。 参考書の答えに Zを整数の集合とし J={}ax+by|x,y∈z} とおく 定義からJは和と整数倍について閉じている a∈J,b∈J と書いてるのですがよく分かりません。 考え方など教えて貰えたら嬉しいです

共感・応援の気持ちを伝えよう!

みんなの回答

  • 回答No.1
  • take_5
  • ベストアンサー率30% (149/488)

この問題のベースには、以下のユークリッドの互除法があります。 それを集合論で焼きなおしたものです。 整数係数のx、yの一次方程式 ax+by=cは、cがaとbの最大公約数の倍数のとき解を持ち、又解を持つのはその時に限る。 ax+by=1 ‥‥(1)を満たす整数x、yの特別値を各々α、βとする。 従って、aα+bβ=1 ‥‥(2) (1)-(2)より a(x-α)=b(β-y)‥‥(3)。 x-αとβ-yは共に整数であるから、a=bの時は (1)は a(x+y)=1となり 整数x、yの値はない。 a≠bの時は (3)を満たす整数x、yの値が存在するためには a,bはお互いに素である。 a、bがお互いに素でない場合を考えてください。例えば、a=2、b=4の時。 逆に、a,bはお互いに素である時に (1)は整数値を持つ。 このとき、mを整数として、x-α=bm、β-y=amが一般解である。

共感・感謝の気持ちを伝えよう!

質問者からの補足

ありがとうございます

関連するQ&A

  • 証明について

    a,bを整数とするとき次の2つの条件(i),(ii)について(i)と(ii)は同値であることを証明する問題です。 (i) a,bはお互いに素である。すなわち、aとbの最大公約数は1である。 (ii) ax(0)+by(0)=1となる2つの整数x(0),y(0)が存在する。 (i)の問題について 2つの整数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となる2つの整数x(0),y(0)が存在はどのように証明するのでしょうか?

  • 証明

    a,bを整数とするとき次の2つの条件(i),(ii)について(i)と(ii)は同値であることを証明する問題です。 (i) a,bはお互いに素である。すなわち、aとbの最大公約数は1である。 (ii) ax(0)+by(0)=1となる2つの整数x(0),y(0)が存在する。 ★(i)⇒(ii)の証明について ○a, 2a, 3a, …, (b-1)aというb-1個のb-1が分かりません。どうしてb-1と考えるのでしょうか? また、b-1ではなくnと置いてもいいですか? ○(1≦k<l≦b-1)の範囲がどのように現れたのでしょうか? ○差la-ka=(l-k)aはbで割り切れると分かるのですか? ○、1≦k<l≦b-1から1≦l-k≦b-2がどうして現れるのか分かりません ○k-lはbで割り切れないのですか? またk-lはどこから現れたのですか? ○kaをbで割った余りが1であるような整数kが存在するのkaはどこから現れたのですか? ○ka-lb=1となるとax(0)+by(0)=1となる2つの整数x(0),y(0)が存在することが分かりません ○x(0)=k,y(0)=-lはどこから出たのですか? ★(ii)⇒(i)の証明 aとbが共通の素因子pをもつと仮定すると、ax+byはいつもpの倍数になるので、ax+by=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とbの最大公約数、(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をa=b=0でない2つの整数とする。a,bの公約数の集合の中の最

    aとbをa=b=0でない2つの整数とする。a,bの公約数の集合の中の最大数dを、aとbの最大公約数といい、 d=(a,b)とかく 例えば(6,4)=2 このときar+bs=(a,b)のような整数rとsが存在するというのを証明する。という問題です、教えてください。

  • 高校数学 証明

    どうしても自力では解けないので、よろしくお願いします; ●整数x,yにたいして   a=5x+4y   b=6x+5y を考える。 (1)(x,y)はaの約数であることを証明せよ (2)(x,y)≦(a,b)を証明せよ (3)(a,b)≦(x,y)を証明せよ よって、(2)(3)より、(a,b)=(x,y)が示せる。  ただし、(x,y)は、整数x,yの最大公約数を意味する。 1問だけでもいいので、もし解けたら教えていただきたいです; よろしくお願いします。

  • 息子の数学です。

    3でわると2余り、5でわると3余り、7でわると4余る3桁の整数は何個あり、最も大きいものは~である。 2つの2桁の自然数があり、その最大公約数が6で最小公倍数が、270である。自然数の組みは? 2つの2桁の自然数があり、最大公約数が8で和が120である2つの自然数の組みを全て求めよ。 なんですが、簡単な出しかたわかる方、教えて下さい。

  • 最大公約数

    最大公約数をだしたいとき、整数なら因数分解すればいいのは分かるんですが例えばax+b,cx+dの最大公約数を求めるようなときはどうすればよいのですか?

  • ユークリッドの互除法

    二つの整数a,bの最大公約数dを、ユークリッドの互除法で求める方法は分かります。 そうして求めたdは、適当な数x,yを使い、d=ax+byで表せることも何とか分かります。 しかし、d=ax+byが与えられたとき、ユークリッドの互除法を使って、特殊解xとyをどうやって求めたらよいのかが分かりません。 これまでの書き込みを見ても理解ができませんでした。 どなたか分かりやすくお教えください。

  • 最大公約数に関する問題です。

    最大公約数に関する問題です。 『2つの整数6186と4709の最大公約数(6189,4709)を求めよ。また、この最大公約数に対して、(6189,4709) = 6186X + 4709YとなるX,Yを見つけよ。』という問題です。最大公約数は1と求められたのですが、後半の『(6189,4709) = 6186X + 4709YとなるX,Yを見つけよ。』は、X,Y の組み合わせが無数にあると思うのですが、どうしたら良いのでしょうか?宜しくお願い致します。

  • 3数の最大公約数

    2つの整数の最大公約数は分かるのですが、3つの整数の最大公約数は分かりません。 ご教授宜しくお願いします。