解説3行目。なぜ4でわって3余る素因数が存在しないことが言えているのでしょうか。

解説3行目。なぜ4でわって3余る素因数が存在しないことが言えているのでしょうか。

No.14 回答者： ありものがたり 回答日時： 2024/12/31 11:22

ああ、そうか。

その第一補充則の証明が必要なのか。

「オイラーの基準」ってのがあって、
奇素数 p と、p とは素な整数 a について
( a/p ) ≡ a^{ (p-1)/2 } (mod p) です。

a = -1 の場合を考えれば
( -1/p ) ≡ (-1)^{ (p-1)/2 } (mod p) であり、
( -1/p ) の値は 1 か -1 ですから
( -1/p ) = (-1)^{ (p-1)/2 } になります。

オイラーの基準の証明は...

( a/p ) = 1　⇒　a^{ (p-1)/2 } ≡ 1 (mod p)　について：
( a/p ) = 1 ならば、 a ≡ x^2 (mod p) となる整数 x が存在する。　
a^{ (p-1)/2 } ≡ (x^2)^{ (p-1)/2 } = x^(p-1).
フェルマーの小定理より、 x^(p-1) ≡ 1 (mod p).

( a/p ) = -1　⇒　a^{ (p-1)/2 } ≡ -1 (mod p)　について：
p が素数であることから剰余環 Z/pZ は体となり、
x = 1, 2, ..., p-1 の各 x に対して、 xy ≡ a (mod p) となる y が存在する。
異なる x には異なる y が対応し、 a が平方非剰余であることから x ≠ y.
よって 1, 2, ..., p-1 は、積が a になる対の (p-1)/2 組に分けられる。
それらの総積をとると、 (p-1)！ ≡ a^{ (p-1)/2 } (mod p).
ウィルソンの定理より、(p-1)！ ≡ -1 (mod p).

No.13 回答者： ありものがたり 回答日時： 2024/12/29 22:44

素数 p と、 p とは互いに素な整数 a に対して、

r^2 ≡ a (mpd p) となる整数 r が存在するとき
　a は mod p の平方剰余であるといい、 ( a/p ) = 1 と書く。
r^2 ≡ a (mpd p) となる整数 r が存在しないとき
　a は mod p の平方非剰余であるといい、 ( a/p ) = -1 と書く。
a が p と互いに素でないときは ( a/p ) = 0 と書く。

この記号 ( a/p ) は ルジャンドルの記号 と呼ばれ、
以下の性質を持つ。
[0]　奇素数 p と整数 a,b に対して ( ab/p ) = ( a/p )( b/p).
[1]　奇素数 p に対して ( -1/p ) = (-1)^{ (p-1)/2 }.
[2]　奇素数 p に対して ( 2/p ) = (-1)^{ (p^2-1)/8 }.
[3]　奇素数 p と素数 q に対して ( q/p )( p/q ) = (-1)^{ (p-1)(q-1)/4 }.

[3] が「平方剰余の相互法則」と呼ばれるもの。
[1] はその「第一補充則」、
[2] はその「第二補充則」である。
平方剰余の相互法則は、ガウスのお気に入りの定理で
生涯に 20個(だったっけ？)の別証を見つけたと言われている。
参考↓
https://pc1.math.gakushuin.ac.jp/~shin/html-file …

今回は、第一補充則のみを使って、
p ≡ 3 (mod 4) ならば p = 4k + 3 (k は整数) と書けるから
( -1/p ) = (-1)^{ (p-1)/2 } = (-1)^{ 4k+3-1)/2 } = (-1)^{ 2k+1 } = -1.
これは、 -1 が mod p の平方非剰余であることを意味している。
すなわち、 a^2 ≡ -1 (mod p) となる整数 a は存在しない。

a^2 + 1 ≡ 0 (mod p) となる整数 a は存在しないことになるから、
整数 a に対して a^2 + 1 は p で割り切れない。

No.12 回答者： mtrajcp 回答日時： 2024/12/29 20:52

a^2+1が素因数p≡3(mod4)を持つと仮定すると

a^2+1=mp となる整数mがある
↓両辺から1を引くと
a^2=mp-1
だから
a^2をpで割った余りは-1だから
a^2≡-1 (mod p)

rをpの原始根とすると
r^x≡-1 (mod p)
となるような整数0<x<p-1がある
r^{2x}≡(-1)^2≡1≡r^{p-1} (mod p)
だから
2x=b(p-1) となる整数bがある
0<x<p-1だから
0<2x<2(p-1)だから
0<b(p-1)<2(p-1)だから
0<b<2だから
b=1だから
2x=p-1だから
x=(p-1)/2
↓p=4k+3となる整数kがあるから
x=2k+1
だから
r^{2k+1}≡-1 (mod p)

r^j≡a (mod p)
となるような整数0<j<p-1がある
r^{2j}≡a^2≡-1≡r^{2k+1} (mod p)
だから
2j+c(p-1)=2k+1 となる整数cがある
↓p=4k+3だから
2j+c(4k+2)=2k+1
2{j+c(2k+1)}=2k+1
↓両辺から2kを引くと
2{j+c(2k+1)-k}=1
↓両辺を2で割ると
j+c(2k+1)-k=1/2
となってj+c(2k+1)-kが整数であることに矛盾するから

a^2+1は素因数p≡3(mod4)を持たない

No.11 回答者： mtrajcp 回答日時： 2024/12/29 17:02

a^2+1が素因数p≡3(mod4)を持つと仮定すると

a^2+1=mp となる整数mがある
↓両辺から1を引くと
a^2=mp-1
だから
a^2をpで割った余りは-1だから
a^2≡-1 (mod p)

整数rをpの原始根とすると
r^j≡a (mod p)
となるような整数0≦j<p-1がある

r^{4j}≡a^4≡(-1)^2≡1≡r^{p-1} (mod p)
だから
4j=p-1
↓p=4k+3となる整数kがあるから
4j=4k+2
↓両辺から4kを引くと
4(j-k)=2
↓両辺を4で割ると
j-k=1/2
となってj-kが整数であることに矛盾するから

a^2+1は素因数p≡3(mod4)を持たない

No.10 回答者： mtrajcp 回答日時： 2024/12/28 20:29

a^2+1が素因数p≡3(mod4)を持つと仮定すると

pを4で割った余りが3のときp≡3(mod4)と書くのだから
a^2+1をpで割った余りは0だから
a^2+1≡0(mod p)
と書く

a^2+1=mp となる整数mがある
↓両辺から1を引くと
a^2=mp-1
だから
a^2をpで割った余りは-1だから
a^2≡-1 (mod p)
と書く

-1に対して
a^2≡-1 (mod p)となるようなaが存在するとき
-1はpの平方剰余といい
(-1/p)=1
と書く

-1に対して
a^2≡-1 (mod p)となるようなaが存在しないとき
-1はpの平方非剰余といい
(-1/p)=-1
と書く

-1はpの平方剰余
(-1/p)=1
となってしまうけれども

平方剰余の第1補充則
p が奇素数なら (-1/p)=(-1)^{(p-1)/2}
で
p = 4k+3
だから

(-1/p)
=(-1)^{(p-1)/2}
=(-1)^{(4k+3-1)/2}
=(-1)^{(4k+2)/2}
=(-1)^{2k+1}
=-1

だから
-1はp≡3(mod4)の平方非剰余であることに矛盾するから

a^2+1は素因数p≡3(mod4)を持たない

No.9 回答者： mtrajcp 回答日時： 2024/12/28 17:07

a^2+1が素因数p≡3(mod4)を持つと仮定すると

a^2+1はpの整数倍だから
a^2+1=kp となる整数kがあるから

a^2+1≡0(mod p)
-1≡a^2 (mod p)

だから

-1はpの平方剰余となるけれども

-1がp≡3(mod4)の平方非剰余であることに矛盾するから

a^2+1は素因数p≡3(mod4)を持たない

No.8 回答者： ありものがたり 回答日時： 2024/12/28 14:15

あーなるほど。

平方剰余の第１補充則か。
p が奇素数なら ( -1/p ) = (-1)^{ (p-1)/2 } で、
p = 4k+3 なら (p-1)/2 = 2k+1 は奇数だものね。

No.7 回答者： mtrajcp 回答日時： 2024/12/28 05:42

a^2+1が素因数p=3(mod4)を持つと仮定すると

a^2+1=0(mod p)
-1=a^2 (mod p)

だから

-1はpの平方剰余となるけれども
-1がp=3(mod4)の非平方剰余であることに矛盾するから

a^2+1は素因数p=3(mod4)を持たない

この回答へのお礼

2行目もう少し丁寧に説明していただけますか。なぜ≡0なのでしょうか

お礼日時：2024/12/28 15:38

No.6 回答者： Tacosan 回答日時： 2024/12/27 20:54

「4で割って 3余る素数」の「羃」が偶数になることはありえないんだけどね.

さておき, #5 の Wikipedia にある項では「4で割って 3余る」どの素数も (因数分解したときに) 偶数個出てくる, といっているわけだけど, 実はそこから派生するネタとして
p が 4 で割って 3余る素数であるとき, m^2+n^2 が p の倍数なら m も n の p の倍数
なのだ.

No.5 回答者： cage64 回答日時： 2024/12/27 18:41

問題を見る限り、難問の類だから、有名な定理を使っているのでしょう。

https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%80%8B …
にあるように、２つの平方数の和で表せる数は、4n+1型の素因子しかもちません。
a^2+1は２つの平方数の和ですから、この定理によって、4n+3型の素因子は持ちません。

この回答へのお礼

リンク先の定理では持たないのではなく素因数の冪が偶数といっているのではないのですか

お礼日時：2024/12/27 18:46