整数問題(最大公約数)

$${n}$$を$${2}$$以上の整数とする。$${n}$$以下の正の整数のうち、$${n}$$との最大公約数が$${1}$$となるものの個数を$${E(n)}$$で表す。例えば、$${E(2)=1,E(3)=2,E(4)=2,…,E(10)=4,…}$$である。
（１）$${E(1024)}$$を求めよ。
（２）$${E(2015)}$$を求めよ。
（３）$${m}$$を正の整数とし、$${p}$$と$${q}$$を異なる素数とする。$${n=p^mq^m}$$のとき

$$
\frac{E(n)}{n}\geqq\frac{1}{3}
$$

が成り立つことを示せ。
                              （一橋大）

【前提】
一般に、実数$${(a,b)}$$について、その「最大公約数が$${1}$$となる」とき、$${a,b}$$は、互いに素であると言う。一橋大の出題者は、この表現をあえて避けているらしい。さて、……。

集合$${A,B,C}$$を考える。集合$${A}$$の要素の個数を$${n(A)}$$と表すことにすると、次の関係が成り立つ。

$$
n(A\cup{B})=n(A)+n(B)-n(A\cap{B})\\n(A\cup{B}\cup{C})=n(A)+n(B)+n(C)-n(A\cap{B})-n(B\cap{C})-n(A\cap{C})+n(A\cap{B}\cap{C})
$$

何か規則性がありそう。機会があれば追及したいが、今回は、いったん打ち切る。

【解答】
（１）
$${1024=2^{10}}$$である。
$${2^n}$$以下の正の整数のうち、「$${2^n}$$との最大公約数が$${1}$$になる」ものを列挙しよう。$${\{1,3,5,…,2^n-1\}}$$である。
これは、$${2^n}$$以下の数から$${2}$$で割り切れる数を除いた数（すなわち奇数）である。

$$
E(2^{10})=2^{10}-\frac{2^{10}}{2}=2^{10}(1-\frac{1}{2})=\frac{2^{10}}{2}=512
$$

答:$${\underline{E(1024)=512}}$$

（２）
$${2015=5×13×31}$$である。
$${2015}$$以下の$${i}$$で割り切れる数の個数を$${F(i)}$$とすると、

$$
E(5×13×31)\\=5×13×31-F(5)-F(13)-F(31)\\+F(5×13)+F(13×31)+F(31×5)-F(5×13×31)\\=5×13×31-\frac{5×13×31}{5}-\frac{5×13×31}{13}-\frac{5×13×31}{31}\\+\frac{5×13×31}{5×13}+\frac{5×13×31}{13×31}+\frac{5×13×31}{31×5}-\frac{5×13×31}{5×13×31}\\=5×13×31(1-\frac{1}{5}-\frac{1}{13}-\frac{1}{31}\\+\frac{1}{5×13}+\frac{1}{13×31}+\frac{1}{31×5}-\frac{1}{5×13×31})
$$

きれいな形になった。これは後ほど利用するとして、ここでは計算が容易な途中式を採用する。

$$
E(2015)\\=5×13×31-5×13-5×31-13×31+5+13+31-1\\=2015-65-155-403+48\\=1440
$$

答:$${\underline{E(2015)=1440}}$$

（３）
（１）より、$${E(p^m)=p^m(1-\frac{1}{p}),E(q^m)=q^m(1-\frac{1}{q})}$$、（２）より、$${E(n)=p^mq^m(1-\frac{1}{p}-\frac{1}{q}+\frac{1}{pq})}$$であると考えられる。さらに整理すると、

$$
E(n)=n(1-\frac{1}{p})(1-\frac{1}{q})・・・①
$$

ここで、$${p\neq{q}}$$について、$${p<{q}}$$としても対称性より一般性は損なわれない。すなわち、$${p\geqq2,q\geqq3}$$とすると、

$$
1-\frac{1}{p}\geqq\frac{1}{2}\\1-\frac{1}{q}\geqq\frac{2}{3}
$$

よって、①より

$$
E(n)\geqq\frac{1}{2}･\frac{2}{3}n=\frac{n}{3}
$$

よって、$${\underline{\frac{E(n)}{n}\geqq\frac{1}{3}}}$$ [終]

【コメント】
実に良問です。