数学ナビゲーター掲示板 [One Topic All View / Re[6]: 最大公約数 / Page: 0]

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

[ 最新記事及び返信フォームをトピックトップへ ]

■35373 / inTopicNo.1)

　最大公約数

□投稿者/ おあたく一般人(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] 削除キー/

■35378 / inTopicNo.2)

　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] 削除キー/

■35380 / inTopicNo.3)

　Re[2]: 最大公約数

▲▼■

□投稿者/ おあたく一般人(15回)-(2008/09/02(Tue) 14:42:36)

すみません。WIZさんご指摘通り、問題の書き間違いがありました。
GCM(x,y) > 0でなくて、GCM(x,y) > 1を示せでした。

よろしくお願いいたします。

引用返信/返信 [メール受信/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] 削除キー/

■35388 / inTopicNo.5)

　Re[4]: 最大公約数

▲▼■

□投稿者/ おあたく一般人(16回)-(2008/09/02(Tue) 18:32:53)

WIZさん、ご回答ありがとうございます。

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

よろしくお願いいたします。

引用返信/返信 [メール受信/OFF] 削除キー/

■35390 / inTopicNo.6)

　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] 削除キー/

■35397 / inTopicNo.7)

　Re[6]: 最大公約数

▲▼■

□投稿者/ おあたく一般人(18回)-(2008/09/02(Tue) 23:01:42)

WIZさん、詳しく教えて頂きありがとうございました。

引用返信/返信 [メール受信/OFF] 削除キー/

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

このトピックに書きこむ

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

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