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

21.1

(a) 1+2+3+…+(p-1)=p(p-1)/2≡0 (mod p)。

(b) 1²+2²+3²+…+(p-1) ²=p(p-1)(2p-1)/6≡0 (mod p)。

(c)

(n+1)^k+1-n^k+1=Σ_1≤j≤k a_jn^j+1 (a_k=k+1)をn=1からp-1まで足して、

p ^k+1-1=Σ_1≤j≤k a_j Σ_1≤n≤p-1 n^j+ p-1より、

(k+1)Σ_1≤n≤p-1 n^j= p ^k+1- p-Σ_1≤j≤k-1 a_j Σ_1≤n≤p-1 n^j。

kについての数学的帰納法を使いたいが、k=p-1のときが問題・・・。

21.2

(a)

(i) e₉(2)=6

(ii) e₁₅(2)=4

(iii) e₁₆(3)=4

(iv) e₁₀(3)=4

(b)

e_m(a)がφ(m)を割りきらないなら、φ(m)= qe_m(a)+r (0<r< e_m(a))と書ける。

このとき1≡a^φ(m)= a ^qe_m(a)+r ≡a^rとなり、e_m(a)の最小性に反する。

よって、r=0でなければならないから、e_m(a)| φ(m)。

21.3

(a) e₁₁=10, e₁₃=12, e₁₅=4, e₁₇=8, e₁₉=18。

(b) e_mn=e_me_n/gcd(e_m, e_n)=LCM(e_m, e_n)と予想される。

(c) (b)の通りならe₁₁₂₂₇= e₁₀₃ e₁₀₉ /gcd(e₁₀₃, e₁₀₉)=612

(d)

y≡1 (mod mn)とすると、q∈ℤとしてy=qmn+1だから、

yは連立合同式y≡1 (mod m), y≡1 (mod n) (1)の解である。

gcd(m,n)=1なので、中国の剰余定理により、yは1≤y<mnとなる唯一の解である。

いまg=gcd(e_m, e_n), e_m= e_m'g, e_n= e_n'gとし、x=LCM(e_m, e_n)= e_m'e_n'gとする。

2^x=(2 ^e_m) ^e_n' ≡1 (mod m)また2^x=(2 ^e_n) ^e_m' ≡1 (mod n)だから、

2^xは確かに(1)を満たし、したがってy=2^xはy≡1(mod mn)の唯一の解となる。

もし別のx'= e_mq_m+r_m>0に対しy=2^x'≡1 (mod mn)となるとすると、

mod mで1≡2^x'≡2 ^r_mで、e_mの最小性からr_m=0なのでe_m| x'である。

同様にe_n| x'だから、x'はe_m, e_nの公倍数なので、x'≥x=lcm(e_m, e_n)。

したがって、x= LCM(e_m, e_n)は(1)を満たすy=2^x≡1 (mod mn)を与える、

0でない最小のxである。ゆえにx= e_mn。

（なんかまわりくどい・・・）

(e)

e_p^k=pe_p^k-1=…=p^k-1e_pと予想され、もしそうならe₆₈₉₂₁=41²e₄₁=33620。

(f)

mod p^kでe_p^k=p^k-1e_pとし、数学的帰納法を用いる。k=1の時は明らか。

2^x≡1 (mod p^k+1 )とすると、a∈ℤとして2^x=ap^k+1+1≡1 (mod p^k )だから、

e_p^kの最小性からx≥ e_p^k。x= e_p^kq_k+r_k (q_k>0, 0≤r_k<e_p^k)とすると、

mod p^kで1≡2^x≡2^r_k なので、e_p^kの最小性からr_k =0だから、x= e_p^kq_kである。

2 ^e_pk=bp^k+1 (b∈ℤ)から、2^x=(bp^k+1)^q_k=b^q_kp^kq_k+...+q_k bp^k+1≡1 (mod p^k+1 )となるためには、

（展開のpの最低次の項q_k bp^kのpの次数）≥k+1でなければならない。

したがってq_k≥ pなので、x≥e_p^k+1= pe_p^k= p^ke_pとなり、mod p^k+1でも成り立つ。

21.4

(a) 2, 6, 7, 11のφ(13-1)=4個。

(b)

d=2: 12

d=3: 3, 9,

d=4: 5,8

d=6: 4, 10

d=12: 2, 6, 7, 11