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

10.2


3750=2·3·5⁴なので、gcd(3750,n)≠1となるn∈ℕは2,3,5の倍数。
lcm(2,3,5)=30で、30までの自然数の中に2,3,5の倍数は22個あるから、
φ(3750)=3750·(30-22)/30=1000。
Eulerの公式から、
a≡7³⁰⁰³=(7^φ(3750))³·7³≡7³=343 (mod 3750)
7|343なのでa≠343。gcd(3750,7)=1なので、a=343+3750=4093。


10.3
(a)
Fermatの小定理により、
a⁵⁶⁰=(a²)²⁸⁰≡1 (mod3), a⁵⁶⁰=(a¹⁰)⁵⁶≡1 (mod 11), a⁵⁶⁰=(a¹⁶)²⁵≡1 (mod 17)。
a⁵⁶⁰=3q₁+1=11q₂+1=17q₃+1 (q_1,q_2,q₃∈ℕ)なので、
a⁵⁶⁰=3·11·17q+1=561q+1 (q∈ℕ)。
したがってa⁵⁶⁰≡1 (mod 561)となり、561はCarmichael数。



(b)
561, 1105, 1729, 2465...無数にある。
詳しくはウィキペ。