シルヴァーマン 「はじめての数論」第3版 第25章練習問題

25.1

(a) 1 (b) -1 (c) 1 (d) -1

25.2

与式から(2x-3)²≡13 (mod 31957)で31957は素数。

(13/31957)=1なので解を持つ。

25.3

...

25.4

A²≡5 (mod p)なので、5はpを法とした平方剰余だから(5/p)=(p/5)=1。

p≠5だからp≡1, 2, 3, 4 (mod 5)のいずれか。

p≡1, 4 (mod 5)のときは(p/5)=1なので5は平方剰余である。

p≡2(mod 5)のときは(p/5)=(2/5)=-1。p≡3(mod 5)のときは(p/5)=(3/5)=(5/3)=(2/3)=-1。

したがって、p≡2, 3 (mod 5)のときは5はpを法とした平方剰余にならないので、

p≡1, 4 (mod 5)。

25.6

(a)

p≡3 (mod 4)なら、(p+1)/4は整数になる。このときx²=a^(p+1)/2=a^(p-1)/2+1。

aは平方剰余だからpを法とした原始根をg、自然数をlとしてa=g^2lと書ける。

するとa^(p-1)/2=g^(p-1）≡1 (mod p)なので、x²≡a (mod p) だから、確かに解である。

(b)

(a)の解を具体的に計算してx≡105 (mod 787)

25.7

(a)

p≡5 (mod 8)なら、(p+3)/8, (p-5)/8は整数になる。

aは平方剰余だからpを法とした原始根gの偶数冪。

aは平方剰余だからpを法とした原始根をg、自然数をlとしてa=g^2lと書ける。

x=2a(4a)^(p-5)/8とおくと、x²=a(4a)^(p-1)/4= a·2^(p-1)/2 g^(p-1)l/2 ≡(-1) ^l2^(p-1)/2a (mod p)なので、

lが奇数なら2がpを法とした原始根(2^(p-1)/2≡-1 (mod p))のとき、

lが偶数なら2がpを法とした原始根でない(2^(p-1)/2≡1 (mod p))ときに、

x=2a(4a)^(p-5)/8は解である。

また、lが偶数ならl/2を改めてlと書いてa=g^4lのとき、x= a^(p+3)/8とおけば

x²= a^(p-1)/4+1= ag^(p-1)l≡a (mod p)なので、この場合はx= a^(p+3)/8も解である。

（lが奇数で2がpを法とした原始根でないときはgをとり直すのかな・・・）

(b)

541≡5 (mod 8)なので、(a)からx≡87 (mod 541)またはx≡345 (mod 541)だが、

87²≡536≡-5 (mod 541)なので解はx≡345 (mod 541)。

(c)

653≡5 (mod 8)なので、(a)からx≡288 (mod 653)またはx≡186 (mod 653)だが、

186²≡640 (mod 653)なので解はx≡288 (mod 653)。

25.8

(a) x≡494 (mod 1021)。(b) x≡858 (mod 1021)。(c) (31/1021)=-1なので解なし。

25.9

(a)

(11/1729)=-1、11⁸⁶⁴≡1 (mod 1729)なので一致しないから、

Eulerの基準の対偶から1729は素数ではない。

実際1729=7·13·29でCarmichael数である。

(b)

2^{(1293337-1)/2}≡429596≠± 1(mod 1293337)なので、
Eulerの基準の対偶から1293337は素数ではない。

実際1293337=569·2273である。
なお2^1293336≡1 (mod 1293337)で、2を底としたFermatテストには

たまたま合格してしまう。