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

24.1

(a) 5987≡3 (mod 4)なので解はない。

(b) x²≡6780≡-1 (mod 6781)で、6781≡1 (mod 4)なので解をもつ。

(c) 与式から[2(x+7)]²≡-1 (mod 337)。337≡1 (mod 4)なので解をもつ。

(d) 与式から(x-32)²≡9² (mod 3011)となり解x≡41 (mod 3011)を持つ。

24.2

p₁=17

次のステップは

(2p₁)²+1=1157=13·89

p₂=13

p₃=89

(2p₁ p₂ p₃)²+1= 1547478245=5·1889·163841

p₄=5

p₅=1889

p₆=163841

(2p₁ p₂ p₃ p₄ p₅ p₆)²+1= 3705729002910847051107276101

=293·2037·18713·222544992511819997

p₇= 293

p₈= 3037

p₉= 18713

Rabin-Miller判定では222544992511819997は合成数だが・・・

24.3

m=12でパターンが現れる。

3が平方剰余となる法pについて、p≡±1(mod 12)。

3が非剰余となる法pについて、p≡5(mod 12)またはp≡7 (mod 12)。

24.4

p≡1(mod 8)すなわちp=8k+9の場合、(p-1)/2=4k+4なので、

定理24.4の証明と同様の分割は

2, 4, 6, ..., (4k+4)| (4k+6), ..., (8k+8)

となる。垂直線の右にあるのは[(8k+8)-(4k+4)]/2=2k+2個だから、

2^(p-1)/2≡(-1) ^2k+2≡1 (mod p)

したがってEulerの基準から2は平方剰余。

p≡5(mod 8)すなわちp=8k+5の場合、(p-1)/2=4k+2なので、

定理24.4の証明と同様の分割は

2, 4, 6, ..., (4k+2)| (4k+4), ..., (8k+4)

となる。垂直線の右にあるのは[(8k+4)-(4k+2)]/2=2k+1個だから、

2^(p-1)/2≡(-1) ^2k+1≡-1 (mod p)

したがってEulerの基準から2は非剰余。

24.5

負の数をどうやって簡単に数えればいいか・・・。

24.6

q=4k+1とすると、p=8k+3≡3 (mod4)であるから、

定理24.4により2はpを法とした平方剰余ではない。

いま2がpを法とした原始根でないと仮定すると、

Fermatの小定理により2^p-1≡2^2q≡1 (mod p)で、qは素数だから、

定理21.1により2²≡1 (mod p)または2^q≡1 (mod p)である。

p≥5だから2²≡4 (mod p)となり前者はありえないので、2^q≡1 (mod p)。

すると2^q+1=(2^2k+1)²≡2 (mod p)となるので、2は平方根2^2k+1をもつ。

すなわち2はpを法とした平方剰余となり矛盾。

したがって、2はpを法とした原始根である。