Question

第1志望に合格したい。

(1)の解説についてわからないところがあります。
1024以下の数で互いに素でない個数はどうして、2^9で求めることができるのですか。

演習問題 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

整数

Answer 1

✨ 最佳解答 ✨

アライグマ

1024と互いに素でないというのは1024と1より大きい公約数を持つということです。解説にあるように、1024=2^10ですから、1より大きい公約数をもつとすればそれは必ず2の倍数になります。よって、1024と互いに素でない数は必ず2の倍数であり、逆に2の倍数であれば1024と少なくとも2を公約数として持ち互いに素ではありません。したがって、1024以下の自然数で2の倍数の個数を求めれば良いことになります。これは、先に書いたように1024=2^10=2×2^9ですのでその個数は2^9個になります。

第1志望に合格したい。

なるほど、分かりました。
ありがとうございます。