数学ナビゲーター掲示板
(現在 過去ログ4 を表示中)

HOME HELP 新規作成 新着記事 トピック表示 発言ランク ファイル一覧 検索 過去ログ

[ 親記事をトピックトップへ ]

このトピックに書きこむ

過去ログには書き込み不可

■35397 / inTopicNo.1)  Re[6]: 最大公約数
  
□投稿者/ おあたく 一般人(18回)-(2008/09/02(Tue) 23:01:42)
    WIZさん、詳しく教えて頂きありがとうございました。
引用返信/返信 [メール受信/OFF] 削除キー/
■35390 / inTopicNo.2)  Re[5]: 最大公約数
□投稿者/ WIZ ベテラン(221回)-(2008/09/02(Tue) 20:08:02)
    nを自然数、x,yを整数として、n = x^2+y^2とします。
    既に証明した通り、pが4k+3型の素数で、nがpで割り切れるのならば、GCM(x,y) > 1です。

    対偶を取れば、GCM(x,y) > 1でないのならば、nの因数に4k+3型の素数は無いと言えます。
    # 「GCM(x,y) > 1でない」は「GCM(x,y) = 1である」と等価です。

    GCM(x,y) = g > 1とします。x = Xg, y = Ygとおくと、GCM(X,Y) = 1です。
    n = (g^2)(X^2+Y^2)となります。

    GCM(X,Y) = 1ですから、X^2+Y^2の因数に4k+3型の素数はありません。
    よって、pはg^2の約数、すなわちpはgの約数ということになります。
    以上から、nはp^2(正確にはpの偶数乗)で割り切れると言えます。
引用返信/返信 [メール受信/OFF] 削除キー/
■35388 / inTopicNo.3)  Re[4]: 最大公約数
□投稿者/ おあたく 一般人(16回)-(2008/09/02(Tue) 18:32:53)
    WIZさん、ご回答ありがとうございます。

    nがp^2で割り切れるかどうかに関係無く証明できるのですね。
    でも、自分の直感としてはnはp^2で割り切れると思うのですが、
    こちらも証明可能でしょうか?

    よろしくお願いいたします。
引用返信/返信 [メール受信/OFF] 削除キー/
■35386 / inTopicNo.4)  Re[3]: 最大公約数
□投稿者/ WIZ ベテラン(219回)-(2008/09/02(Tue) 17:03:43)
    背理法で証明します。
    GCM(x,y) = 1と仮定します。

    もし、x ≡ 0 (mod p)とすると、n ≡ 0 (mod p)より、y ≡ 0 (mod p)となります。
    GCM(x,y) ≡ 0 (mod p)より、GCM(x,y) ≧ pとなって矛盾です。
    よって、xもyもpでは割り切れないといえます。

    GCM(x,p) = 1ですから、整数a,bでax+bp = 1を満たすものが存在します。
    # 有理整数は単項イデアル整域なので。

    axy+bpy = yとなりますが、変形して(bp-1)y = (ay)*xより、-y ≡ (ay)*x (mod p)
    よってx^2+y^2 ≡ (x^2)*(1+(ay)^2) ≡ 0 (mod p)を得ます。

    xはpでは割り切れないので、1+(ay)^2 ≡ 0 (mod p)となりますが、
    これは、-1 ≡ (ay)^2 (mod p)となり、-1がpの平方剰余ということと同じです。

    ここで、素数pはp ≡ 3 (mod 4)ですから、-1はpの平方非剰余であり矛盾です。
    よって仮定が誤りであり、GCM(x,y) > 1でなくてはなりません。
引用返信/返信 [メール受信/OFF] 削除キー/
■35380 / inTopicNo.5)  Re[2]: 最大公約数
□投稿者/ おあたく 一般人(15回)-(2008/09/02(Tue) 14:42:36)
    すみません。WIZさんご指摘通り、問題の書き間違いがありました。
    GCM(x,y) > 0でなくて、GCM(x,y) > 1を示せでした。

    よろしくお願いいたします。
引用返信/返信 [メール受信/OFF] 削除キー/
■35378 / inTopicNo.6)  Re[1]: 最大公約数
□投稿者/ WIZ ベテラン(217回)-(2008/09/02(Tue) 12:36:42)
    nが自然数で、x,yが整数で、n = x^2+y^2ならば、GCM(x,y) > 0は自明に近いと思いますが。
    x,yの少なくとも一方は0でないですから、最大公約数は1以上ですよね。

    また、nが4k+3型の素数で割り切れることがどう関係しているのか分かりません。
    何か問題の書き間違いはありませんか?
引用返信/返信 [メール受信/OFF] 削除キー/
■35373 / inTopicNo.7)  最大公約数
□投稿者/ おあたく 一般人(14回)-(2008/09/02(Tue) 08:21:42)
    自然数nは、整数xとyを用いてn = x^2+y^2と表すことができるものとする。
    素数pがp ≡ 3 (mod4)で、n ≡ 0 (mod p)ならば、GCM(x,y) > 0であることを示せ。

    という問題で、p ≡ 3 (mod4)となる素数pは2つの平方数の和に表せないので、
    nはp^2で割り切れないといけないと思います。
    このことからGCM(x^2,y^2) ≡ 0 (mod p^2) ⇒ GCM(x,y) ≡ 0 (mod p) ⇒ GCM(x,y) ≧ p
    となると思うのですが、もっとスカッとした証明はないでしょうか?

    よろしくお願いします。
引用返信/返信 [メール受信/OFF] 削除キー/



トピック内ページ移動 / << 0 >>
Mode/  Pass/

HOME HELP 新規作成 新着記事 トピック表示 発言ランク ファイル一覧 検索 過去ログ

- Child Tree -
Edit By 数学ナビゲーター