整数の問題なんですが

質問

次の問題が解けません。
「X^2+7≡0 mod p
を満たす解のある素数 p>7 を考える。
p mod 14 はいくつか」
手作業でやってみたところ、
1,7,9,11
が出てきましたが、それ以上のことは分かりません。
解き方の分かる方教えてください。

回答No.1

shushou

ルジャンドル指標とか平方剰余の相互法則はご存知でしょうか。

aとpが互いに素のときルジャンドル指標(a/p)を次のように定義します。
x^2≡a　mod p　が解を持つとき　　(a/p)=1
x^2≡a　mod p　が解を持たないとき(a/p)=-1

平方剰余の相互法則とは次の定理のことです。
pとqを相異なる３以上の素数とするとき次が成り立つ。
pとqの少なくともどちらか一方が４で和って１余る素数のとき　(q/p)=(p/q)
pとqが両方とも４でわって３余る素数のとき　(q/p)=-(p/q)

また、次も成り立ちます。
（ア）(a^2/p)=1
（イ）((pn+a)/p)=(a/p)
（ウ）(ab/p)=(a/p)(b/p)
（エ）pが４で割って１余るとき(-1/p)=1
pが４で割って３余るとき(-1/p)=-1
（オ）(2/p)=(-1)^{(p^2-1)/8}

では、
＞「X^2+7≡0 mod　p を満たす解のある素数 p>7 を考える。
＞p mod 14 はいくつか」
を解きましょう。
まず、p mod 14 で答えの可能性があるのは
p≡1,3,5,9,11,13　だけですね。だからこの６通りについて
X^2+7≡0 mod　p すなわち、X^2≡-7 mod　p
が解を持つのかどうか考えれば良いですね。
つまり(-7/p)=1になるpを６通りの中から探せばよいのです。
ところで
(-7/p)=(-1/p)(7/p)　　（（ウ）より）ですが
pが４で割って１余るとき
　　　=1*(p/7)=(p/7)　　（（エ）と相互法則より）
pが４で割って３余るとき
　　　=(-1)*(-(p/7))=(p/7)
ですから結局、(p/7)=1となるpを６通りの中から探すことになります。
（ア）よりp≡1,9 mod14のときは(p/7)=1になりますね。
p≡3のとき
(p/7)=((14k+3)/7)=(3/7)　　（（イ）より）
=-(7/3)=-(1/3)=-1
p≡5のとき
(p/7)=((14k+5)/7)=(5/7)=(7/5)=(2/5)=(-1)^{(5^2-1)/8}=-1
p≡11のとき
(p/7)=(11/7)=(4/7)=(2^2/7)=1
p≡13のとき
(p/7)=(13/7)=(-1/7)=-1
以上より答えはp≡1,9,11　mod14　となります。