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

21.5

(a)

pは素数なので、F(X)の因数となる既約多項式のどれか1つが、

0と合同でなければならない。

F(X) ≡0 (mod p)の異なる解の数が最大となるのは、p≥Dかつ、

F(X)が(X-X_D)(X-X_D-1)... (X-X₁)と因数分解されて

X_i≡0 (mod p) (1≤i≤D), X_i≢X_j (i≠j)となるときである。

このとき0≤X<pとなる異なる解の数はD個。

(b)

X⁴+5X³+4X²-6X-4=(X-1)(X+2)(X²+4X+2)なので、

0≤X<11となる解はX≡1 (mod 11)とX≡9 (mod 11)の2つ。

(c)

8は素数でないので、(a)とは矛盾せず、8の因数をX+1とX-1が因数として含むXも解である。

解はX≡1 (mod 8), X≡3 (mod 8), X≡5 (mod 8), X≡7 (mod 8)の4つ。

21.6

(a) g⁵とg⁷

(b)

gの冪g^k (k>1)についてgcd(k,p-1)=h>1なら、k=k'h, p-1=qhとして

Fermatの小定理により(g^k)^q=(g^p-1)^k'≡1 (mod p)なので、

g^k はpを法とした原始根ではない。

対偶を取れば、g^kがpを法とした原始根ならgcd(k,p-1)=1。

逆にpを法とした原始根gに対しgcd(k,p-1)=1となるkをとり、冪g^kを考える。

g^kが原始根でなく、位数がx (0<x<p-1)とする。すなわち(g^k)^x≡1 (mod p)となる。

gcd(k,p-1)=1だからあるu,v∈ℤが存在してku=1+(p-1)vなので、

1≡[(g^k)^x]^u≡g^x (mod p)となり、gも原始根でないことになるので矛盾。

したがって、gcd(k,p-1)=1ならg^kもpを法とした原始根。

以上により、pを法とした原始根gに対し、

g^kもpを法とした原始根となる必要十分条件は、

gcd(k,p-1)=1となることである。

(c) 21169-1=21168=2⁴·3³·7² から、(b)により原始根はg⁵, g¹¹, g¹³, g¹⁷, g¹⁹。

21.7

(a) 5, 7, 17, 19

(b) 5, 7, 17, 19, 29, 31, 43, 53, 79, 89

21.8

bが原始根でなければ明らかにa=b²は原始根でないから、

bはp-1を法とした原始根とする。pは奇素数なのでp-1は偶数。

mod pで1≡b^p-1=a^(p-1)/2だから、aの位数は(p-1)/2となりaは原始根でない。