• 締切済み

証明について

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)が存在はどのように証明するのでしょうか?

みんなの回答

回答No.3

(1)a, 2a, 3a, …, (b-1)aというb-1個の整数をbで割った余りは全て異なることを証明します。 a, 2a, 3a, …, (b-1)aの中でbで割った余りが等しい2数があったと仮定します。それをkaとlaとします(1≦k<l≦b-1)。これらの差la-ka=(l-k)aはbで割り切れるはずですが、aとbは互いに素なので、k-lがbで割り切れることになります。しかし、1≦k<l≦b-1から1≦l-k≦b-2なので、k-lはbで割り切れません。よって背理法により示されました。 (2)「kaをbで割った余りが1であるような整数kが存在する。これを式で書くとおしまい。」の部分を補足します。 「kaをbで割った余りが1であるような整数kが存在する」というのは、「ka=lb+1となる整数k,lが存在する」ということです。lbを移項するとka-lb=1となるので、ax(0)+by(0)=1となる2つの整数x(0),y(0)が存在することになります。x(0)=k,y(0)=-lです。(ちなみに、ここでのk,lは(1)でのk,lとは何の関係もありません。) (3)「36を素因数分解すると36 = 2^2 × 3^2。共通の素因数Pが12となるのでしょうか?」という質問について 質問の意味が分かりかねます。どういう意味でしょうか。「共通の素因子」というのは2つの整数に対して使っています。先ほどの回答では「aとbの共通の素因子」という意味でした。

suika_11
質問者

補足

解説ありがとうございます。 分からない点があるので、もう少しお付き合いしてください。 ○a, 2a, 3a, …, (b-1)aという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となることはない。もちろんx,yは整数について、 具体的に把握することができないので例えば数字を使った表現を利用することができるのでしょうか? 沢山質問をしてすいません。

回答No.2

有名な性質です。 (i)⇒(ii)の証明 a, 2a, 3a, …, (b-1)aというb-1個の整数はどれもbで割り切れないから(aとbが互いに素だから)、その余りは1からb-1までであるが、これらの数をbで割った余りは全て異なるので(←証明してください。分からなかったら聞いてください。)、これらの数をbで割った余りには1からb-1までの数が1回ずつ現れる。よって、kaをbで割った余りが1であるような整数kが存在する。これを式で書くとおしまい。(←分からなかったら聞いてください。) (ii)⇒(i)の証明 aとbが共通の素因子pをもつと仮定すると、ax+byはいつもpの倍数になるので、ax+by=1となることはない。もちろんx,yは整数です。

suika_11
質問者

補足

(i)⇒(ii)の証明 の証明はよく分からないので教えてください。 それから、 (ii)⇒(i)の証明もよく分かりません。 例えば 36を素因数分解すると 36 = 2^2 × 3^2 共通の素因数Pが12となるのでしょうか? よく分からないのでこちらも教えて頂けれたら嬉しいです

  • oyamala
  • ベストアンサー率40% (8/20)
回答No.1

質問者さんは(i)の問題と(ii)の問題があるように思っていらっしゃるように思われますが・・・、 問題は(i)⇔(ii)を示せって言ってるわけで、問いが2つあるわけではありません。 互いに素ということは最大公約数が1であるということなのです。 それは証明するとかそういう話ではなくて、そう定義されていることです。 ですから、(i)が成り立つ時に(ii)が成り立つこと、 そして(ii)が成り立つ時に(i)が成り立つことを言えば証明されたわけです。

suika_11
質問者

補足

解説ありがとうございます。 2つ一緒に求めるのですね。 でもどうやって2つを結びつけるのでしょうか?

関連するQ&A

  • 証明

    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 と書いてるのですがよく分かりません。 考え方など教えて貰えたら嬉しいです

  • 証明

    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となることはない。 ことについてよく分かりません。 例えば数字を使った表現を利用することができるのでしょうか? 数字を使っても証明はできるでしょうか? 沢山質問をしてすいません。

  • 整数

    ユークリッドの互除法とa=bq+rを使って次の証明をお願いします。 「a,bは整数とする。(a,b)=1のときax+by=1を満たす整数x,yが存在することを示せ」 (a,b)=1というのは互いに素つまり1以外に公約数を持たないということです。 非常に困っています よろしくお願いします。

  • ユークリッドの互除法について

    こんにちは。高校数学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 ユークリッドの互除法についてです。

    こんにちは。高校数学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”g2,r=r'とする。 ただし、a',b',b”,r'は整数で、a'とb',b”とr'はそれぞれ互いに素である。このとき、 r=a-br=a'g1-b'g1q=(a'-b'q)g1 a'-b'rは整数であるから、g1はrの約数、★すなわちbとrの公約数になる。 以下略 この★の部分がわかりません。 g1がrの約数になると bとrの公約数とも言える理由は何なのでしょうか? どなたかよろしければ ご教授お願い致します。

  • {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)=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)  この定理を使った場合の証明はなりますか。 よろしくお願いしま  す。

  • 高校数学の証明、添削お願いします!

    新高3です。 どなたか以下の証明が合ってるかどうか添削願いますm(__)m 【問い】「aとbが互いに素であるとき、 a^2とb^2が互いに素であることを証明せよ」 【私の答え】 a^2とb^2の最大公約数をGとおくと、 a^2=αG b^2=βG (αとβは互いに素)とおける。 このとき、a>0,b>0だから、 a=√α×√G b=√β×√G となり、aとbは公約数√Gをもつが、 a,bは互いに素より√G=1でなければならない。 ∴G=1    a^2とb^2の最大公約数は1となり、 a^2とb^2は互いに素である。 「最大公約数をG」とおいて、G=1となることを利用する「互いに素の証明」をやってみたかったのですが、なかなか上手く行きません(__)もし違っていましたら、上の方針でどなたか出来る方模範解答を提示してくださるとうれしいです(__)お願いします。

  • 最大公約数 と 互いに素 の関係

    自然数aと自然数bの最大公約数=G  ⇒  自然数a=整数x × G  かつ 自然数b=整数y × G  かつ 整数xと整数yは互いに素 という定理について疑問があります 自然数a=整数x × G  かつ 自然数b=整数y × G  の部分は最大公約数の定義から明らかなのですが 整数xと整数yは互いに素 がなぜこう言えるのかわかりません 教えてください またこれは⇔はなりたつのでしょうか? また自然数a 自然数b ではなく 整数a 整数b といった場合には成り立つのでしょうか? ※ここでは「倍数」、「約数」とうは負の数まで考える定義を採用しています 例:6の約数=-6,-3,-2,-1,1,2,3,6

  • 高校数学 証明

    どうしても自力では解けないので、よろしくお願いします; ●整数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問だけでもいいので、もし解けたら教えていただきたいです; よろしくお願いします。