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

11.11
160=2⁵·5である。
160=2⁴·10=φ(2⁵)φ(11)=φ(352)、2⁴·10=φ(17)φ(11)=φ(187)。
160=1·2⁴·10=φ(2)φ(17)φ(11)=φ(374)。
160=2²·2²·10=φ(2³)φ(5)φ(11)=φ(440)、2²·2²·10=φ(12)φ(5)φ(11)=φ(660)。
160=2·2³·10=φ(3)φ(2⁴)φ(11)=φ(528)
160=2³·20=φ(2⁴)φ(5²)=φ(400)。
160=2·2²·20=φ(3)φ(2³)φ(5²)=φ(600)。
160=2²·40=φ(5)φ(41)=φ(205)、2²·40=φ(2³)φ(41)=φ(328)、2²·40=φ(10)φ(41)=φ(410)、
2²·40=φ(12)φ(41)=φ(492)。
まとめると、187, 205, 328, 352, 374, 400, 410, 440, 492, 528, 600, 660の12個で全て。

(a)

1000=2³·2²。この因数の中で、Euler関数の値域になるのは偶数なので、さらに絞り込むと、

1=φ(2), 2=φ(2²)=φ(3)=φ(2·3),2²=φ(5)=φ(2³)=φ(2·5), 2³=φ(2⁴), 

2·5=φ(11), 2²·5=φ(5³), 2³·5=φ(41),  2²·5²=φ(101),  2·5³=φ(251),  2²·5³=φ(5⁴)

なので、nを割る候補の素数は2, 3, 5, 11, 41, 101, 251。

(b)

1000=1·2·500=φ(2²)φ(5⁴)=φ(2500)

1000=1·2·500=φ(3)φ(5⁴)=φ(1875)

1000=1·2·500=φ(2)φ(3)φ(5⁴)=φ(3750)

1000=1·4·500=φ(2³)φ(251)=φ(2008)

1000=1·4·500=φ(5)φ(251)=φ(1255)

1000=1·4·500=φ(2)φ(5)φ(251)=φ(2510)

1000=1·10·100=φ(11)φ(5³)=φ(1375)

1000=1·10·100=φ(11)φ(101)=φ(1111)

1000=1·10·100=φ(2)φ(11)φ(5³)=φ(2750)

1000=1·10·100=φ(2)φ(11)φ(101)=φ(2222)

1000=1·2·2·250=φ(2²)φ(3)φ(251)=φ(3012)

となり、n=1111, 1255, 1375, 1875, 2008, 2222, 2500, 2510, 2750, 3012, 3750。