- 締切済み
証明について
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)が存在はどのように証明するのでしょうか？
- みんなの回答 （3）
- 専門家の回答
みんなの回答
- seven_triton
- ベストアンサー率41% (10/24)
(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となる２つの整数x(0),y(0)が存在することになります。x(0)=k,y(0)=-lです。（ちなみに、ここでのk,lは(1)でのk,lとは何の関係もありません。） (3)「36を素因数分解すると36 = 2＾2 × 3＾2。共通の素因数Pが１２となるのでしょうか？」という質問について 質問の意味が分かりかねます。どういう意味でしょうか。「共通の素因子」というのは２つの整数に対して使っています。先ほどの回答では「aとbの共通の素因子」という意味でした。
- seven_triton
- ベストアンサー率41% (10/24)
有名な性質です。 (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が１２となるのでしょうか？ よく分からないのでこちらも教えて頂けれたら嬉しいです
- oyamala
- ベストアンサー率40% (8/20)
質問者さんは(i)の問題と(ii)の問題があるように思っていらっしゃるように思われますが・・・、 問題は(i)⇔(ii)を示せって言ってるわけで、問いが2つあるわけではありません。 互いに素ということは最大公約数が1であるということなのです。 それは証明するとかそういう話ではなくて、そう定義されていることです。 ですから、(i)が成り立つ時に(ii)が成り立つこと、 そして(ii)が成り立つ時に(i)が成り立つことを言えば証明されたわけです。
補足
解説ありがとうございます。 ２つ一緒に求めるのですね。 でもどうやって２つを結びつけるのでしょうか？
補足
解説ありがとうございます。 分からない点があるので、もう少しお付き合いしてください。 ○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-ｌはどこから現れたのですか？ ○kaをbで割った余りが1であるような整数kが存在するのkaはどこから現れたのですか？ ○ka-lb=1となるとax(0)+by(0)=1となる２つの整数x(0),y(0)が存在することが分かりません ○x(0)=k,y(0)=-lはどこから出たのですか？ ○(ii)⇒(i)の証明 aとbが共通の素因子pをもつと仮定すると、ax+byはいつもpの倍数になるので、ax+by=1となることはない。もちろんx,yは整数について、 具体的に把握することができないので例えば数字を使った表現を利用することができるのでしょうか？ 沢山質問をしてすいません。