演習問題 4 → 解答 p. 160
を2以上の整数とする. n以下の正の整数のうち, n との最大公約数が1と
なるものの個数を E (n) で表す. 例えば
E(2)=1,E(3)=2, E(4)=2, ., E(10)=4,
である.
(1) E (1024) を求めよ.
(2) (2015) を求めよ. 2013
00
(3)を正の整数とし, pg を異なる素数とする. n=p"q" のとき
E(n) 1
公n 3
が成り立つことを示せ .
の) は2の倍数であり,これは
2°=512 個ある. 会国会
∴.E(1024)=1024-512=512 [
Thes
4 (1) 1024=210 だから, 1024 以下の
自然数の中で1024 との最大公約数が1よ
り大きくなるもの(互いに素ではないも
12.21 だから 2015以下の
(一橋大)
pg の
p, q