https://spherical-harmonics.hateblo.jp/entry/Handai/2024/Rikei

2025.03.10記

[5] 自然数 $1，2，3，\cdots，n$ のうち， $n$ と互いに素であるものの個数を $f(n)$ とする．

(1) 自然数 $a，b，c$ および相異なる素数 $p，q，r$ に対して，等式
$f(p^aq^br^c)=p^{a-1}q^{b-1}r^{c-1}(p-1)(q-1)(r-1)$
が成り立つことを示せ．

(2) $f(n)$ が $n$ の約数となる5以上100以下の自然数 $n$ をすべて求めよ．

本問のテーマ

オイラーの $\varphi$ 関数（トーシェント関数）
エラトステネスの篩
包除原理

2025.03.10記（23:19:18）
エラトステネスの篩の考え方から素数 $p$ の倍数は $p$ 個毎に現れるので， $1$ から $Np$ （ $N$ は自然数）の中に $p$ の倍数（ $p$ と互いに素ではないもの）は丁度 $N$ 個ある．

[解答]
(1) $n=p^aq^br^c$ とする．

$1$ から $n$ までに $p$ の倍数は $\dfrac{n}{p}$ 個あり， $q$ の倍数は $\dfrac{n}{q}$ 個あり， $r$ の倍数は $\dfrac{n}{r}$ 個あり， $pq$ の倍数は $\dfrac{n}{pq}$ 個あり， $pr$ の倍数は $\dfrac{n}{pr}$ 個あり， $qr$ の倍数は $\dfrac{n}{qr}$ 個あり， $pqr$ の倍数は $\dfrac{n}{pqr}$ 個ある．

よって $n$ と互いに素でないものの個数は包除原理により
$\dfrac{n}{p}+\dfrac{n}{q}+\dfrac{n}{r}$ $-\dfrac{n}{pq}-\dfrac{n}{pr}-\dfrac{n}{qr}$ $+\dfrac{n}{pqr}$
となる．よって
$f(n)=n$ $-\dfrac{n}{p}-\dfrac{n}{q}-\dfrac{n}{r}$ $+\dfrac{n}{pq}+\dfrac{n}{pr}+\dfrac{n}{qr}$ $-\dfrac{n}{pqr}$ $=n\left(1-\dfrac{1}{p}\right)\left(1-\dfrac{1}{q}\right)\left(1-\dfrac{1}{r}\right)$ $=p^{a-1}q^{b-1}r^{c-1}(p-1)(q-1)(r-1)$
が成立する．

(2) 素数4つの積は $2\cdot3\cdot5\cdot7=210$ 以上であるから，5以上100以下の自然数 $n$ の素因数の種類は3以下となる．

(i) $n=p^a$ のとき $n=f(n)\cdot\dfrac{p}{p-1}$ であるから $\dfrac{p}{p-1}$ が自然数となれば良く， $p=2$ に限られる．よって $n=8，16，32，64$ である．

(ii) $n=p^aq^b$ （ $p\lt q$ ）のとき $n=f(n)\cdot\dfrac{p}{p-1}\cdot\dfrac{q}{q-1}$ である． $\dfrac{p}{p-1}$ が自然数となるとき（ $p=2$ ）， $q$ は存在しないことと， $p$ と $p-1$ は互いに素， $q$ と $q-1$ は互いに素であるから， $p-1$ は $q$ の約数で， $q-1$ は $p$ の約数となる必要がある．ここで $p，q$ が共に奇数であるとすると $\dfrac{p}{p-1}\cdot\dfrac{q}{q-1}$ は自然数とはならないので不適だから， $p=2$ でなければならない．

このとき $\dfrac{p}{p-1}\cdot\dfrac{q}{q-1}$ $=\dfrac{2q}{q-1}$ が自然数となるのは $q=3$ に限る．よって $n=6，12，24，48，96$ ， $n=18，36，72$ ， $n=54$ である．

(iii) $n=p^aq^br^c$ （ $p\lt q\lt r$ ）のとき $n=f(n)\cdot\dfrac{p}{p-1}\cdot\dfrac{q}{q-1}\cdot\dfrac{r}{r-1}$ である．(ii) と同様にして $p，q，r$ が全て奇数であるとすると不適だから $p=2$ となり，このとき $\dfrac{p}{p-1}\cdot\dfrac{q}{q-1}\cdot\dfrac{r}{r-1}$ $=\dfrac{2q}{q-1}\cdot\dfrac{r}{r-1}$ が整数でなければならないが，分母は偶数×偶数で4の倍数であるが，分子は2×奇数×奇数なので不適．よってこの形で $f(n)$ が $n$ の約数になることはない．

以上から $n=6，8，12，16，18，24，32，36，48，54，64，72，96$ である．

一般の場合も包除原理で求めることができるが
「自然数 $m$ と自然数 $n$ が互いに素ならば $f(mn)=f(m)f(n)$ 」
を示して
$f(p^aq^br^c)$ $=f(p^a)f(q^b)f(r^c)$ $=p^{a-1}(p-1)\cdot q^{b-1}(q-1)\cdot r^{c-1}(r-1)$
を示す証明が良く見られる．