素数に関する質問です。

質問

素数に関する質問です。

aとbが共通因数を持たないならば、a^2＋b^2の奇数の素因数はどれも4n＋1の形をしている。

このことはどのようにして証明できるのでしょうか？

回答No.2

proto · ベストアンサー

n = a^2+b^2
と表される自然数nを考え、nの奇数の素因数のひとつをpとします。

まず、aがpで割り切れる場合を考える。
　　n = a^2+b^2
であるから、法をpとして考えると
　　0 ≡ 0^2+b^2　　(mod p)
　　b^2 ≡ 0　　(mod p)
よって、b^2がpで割り切れるから、bもまたpで割り切れる。
結局aもbもpで割り切れることになり、a,bが共通因数を持たないことに矛盾する。
よってa,b共にpで割り切れないとして考えて良い。

aはpで割り切れず、pは素数であるから、gcd(a,p)=1
(gcd(a,p)はaとpの最大公約数)
よって
　　ax+py ≡ 1
となる整数x,yが存在する。
再びpを法として考えると、
　　ax+0 ≡ 1　　(mod p)
　　ax ≡ 1　　(mod p)
を満たすような整数xが存在する。

いま
　　a^2+b^2 = n
の両辺にx^2を掛けると
　　(ax)^2+(bx)^2 = nx^2
三度pを法として考えると
　　(ax)^2+(bx)^2 ≡ nx^2　　(mod p)
　　1+(bx)^2 ≡ 0　　(mod p)
　　(bx)^2 ≡ -1　　(mod p)

これは合同式
　　X^2 ≡ -1　　(mod p)
がX≡bxを解に持つことを示している。
上の合同式が解を持つ必要十分条件は奇素数pが4k+1型の数であることだから、これによりpが4k+1の形をしていることが示された。

お礼

分かりやすい証明ありがとうございます。

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

回答No.1

yoikagari

a^2＋b^2の奇数の素因数pをとる。
pが4で割ると3余る素数と仮定する。
a^2+b^2≡0 (mod p)

aがpで割り切れると仮定すると
b^2≡0 (mod p)
pは素数だからb≡0 (mod p)
よって、bもpで割り切れる。
したがって、a,bが公約数pを持つことになり
a,bが共通因数を持たないという事実に反するから不合理

bがpで割り切れると仮定すると
a^2≡0 (mod p)
pは素数だからa≡0 (mod p)
よって、aもpで割り切れる。
したがって、a,bが公約数pを持つことになり
a,bが共通因数を持たないという事実に反するから不合理

よってa,bともにpでは割り切れない。

a^2≡-b^2 (mod p)
両辺を(p-1)/2乗すると
a^(p-1)≡(-1)^{(p-1)/2}・b^(p-1) (mod p)
pは4で割ると3余るので、p=4k+3とかける
(-1)^{(p-1)/2}=(-1)^(2k+1)=-1だから
a^(p-1)≡-b^(p-1) (mod p)
a,bはpで割り切れないから、フェルマーの小定理より
a^(p-1)≡b^(p-1)≡1 (mod p)がいえるから
1≡-1 (mod p)となって不合理

これはpが4で割ると3余る素数と仮定したことから起こった。
よって、pは4で割ると1余ることがわかる。

お礼

とても参考になりました。

また是非ご指導お願いします。