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

証明について

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の共通の素因子」という意味でした。

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

質問者からの補足

解説ありがとうございます。 分からない点があるので、もう少しお付き合いしてください。 ○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は整数です。

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

質問者からの補足

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

  • 回答No.1

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

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

質問者からの補足

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

  • {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あまりをrとすると a=bq+r であるので r=a-bq である。ここで、この右辺はa bの最大公約数でわり切れるのは、なぜか教えて下さい。あと a bの最大公約数がrとb の公約数でもあるのはなぜですか?お願いします。

  • 証明したいことを証明の途中に使う

    nとaが互いに素 ⇔ nとn-aが互いに素 の証明で2つ疑問がわいたので、質問します。 nとaの最大公約数をdとおくと n=Nd a=Ad (NとAは互いに素 これは背理法の証明 がインターネットでしらべれました。) とおけます。このときn-a=(N-A)dです。 ここからが疑問です。NとAが互いに素より、NとN-Aも互いに素です。 自分はこの文は、nをN、aをAと置き換えてはいるが証明したいことであり、成り立つかわからないので証明の途中には使っていけないと思いました。証明の続きは、 よってdはnとn-aの最大公約数にもなるから、nとaが互いに素 ⇔ nとn-aが互いに素です。で終わっていますが、2つ目の疑問が残りました、自分はd=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の公約数とも言える理由は何なのでしょうか? どなたかよろしければ ご教授お願い致します。

  • 最大公約数

    2つの正の整数をA、Bとし、AをBで割ったときの商をQ、あまりをRとすれば、A、Bの最大公約数はB、Rの最大公約数に一致するのはなぜですか?

  • 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が存在するというのを証明する。という問題です、教えてください。

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

    新高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となることを利用する「互いに素の証明」をやってみたかったのですが、なかなか上手く行きません(__)もし違っていましたら、上の方針でどなたか出来る方模範解答を提示してくださるとうれしいです(__)お願いします。