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

19.1

(a)

すべての0<a<nに対しa^n-1≡1(mod n)。なので、pの原始根をgとしてa=gでもそうである。

mod pではg^mにおいてp-1| mのときのみg^m≡1(mod p)。

p|nなので、mod nでもg^n-1≡1(mod n)だからp-1| n-1。

(b)

…

19.2

存在したとして、nの2つの素因数をp,q (p>q>2)とすると、

定理19.1からn-1=(p-1)(q-1)n’ (n’ ≥1)と書ける。

これよりn-1=(n-1) n’-(p+q-2)n’>(n-1) n’ ≥ n-1となり矛盾。

したがって、素因数を2つだけとるCarmichael数は存在しない。

19.3

(a) Carmichael数 (b) Carmichael数でない。(c) Carmichael数 (d) Carmichael数

(e) Carmichael数 (f) Carmichael数でない。(g) Carmichael数でない。

(h) Carmichael数でない。(i) Carmichael数 (j) Carmichael数

(k) Carmichael数 (l) Carmichael数

19.4

(a)

定理19.1の条件(1)は明らかに満たされている。

p-1=6k, 12k, 18kは、n-1=36k(36k²+11k+1)を割るから、条件(2)も満たされている。

したがってCarmichael数。

(b)

k=1,6,35,45,51。

19.5

825265=5·7·17·19·73

19.6

(b)

10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361

(c)

997633

19.7

(a)

2⁶⁹ ≡967 (mod 1105)、2^2·69 ≡259 (mod 1105)、

2^4·69 ≡781 (mod 1105)、2^8·69≡1 (mod 1105)で合成数。

(b)

294409-1=2³·36801。

2³⁶⁸⁰¹ ≡512 (mod 294409)、2^2·36801 ≡262144 (mod 294409)、

2^4·36801 ≡1 (mod 294409)で合成数。

294409=37·73·109, 36|294408, 72|294408, 108|294408なのでCarmichael数。


(c)
118901521=271·541·811, 270|118901520, 540|118901520, 810|118901520なのでCarmichael数。


19.8
(a) 素数
(b) 合成数
(c) 合成数
(d) 素数