自然数 1, 2, 3, \cdots, n のうち，n と互いに素であるものの個数を f(n) とする。
(1) 自然数 a, b, c および相異なる素数 p, q, r に対して，等式
\begin{aligned} &f(p^aq^br^c) \\ &= p^{a-1}q^{b-1}r^{c-1}(p-1)(q-1)(r-1) \end{aligned}
が成り立つことを示せ。
(2) f(n) が n の約数となる 5 以上 100 以下の自然数 n をすべて求めよ。
N = p^aq^br^c とおく。N の素因数は p、q、r だけだから、1 から N までのうち N と互いに素でない数は、p、q、r のどれかで割り切れる数です。
1 から N までに p の倍数は \dfrac{N}{p} 個、p と q の両方の倍数は \dfrac{N}{pq} 個、3 つすべての倍数は \dfrac{N}{pqr} 個ある。重なりを足し引きして数えます。
\begin{aligned} f(N) &= N - \left(\dfrac{N}{p} + \dfrac{N}{q} + \dfrac{N}{r}\right) \\ &\quad + \left(\dfrac{N}{pq} + \dfrac{N}{qr} + \dfrac{N}{rp}\right) - \dfrac{N}{pqr} \end{aligned}
右辺は N\left(1 - \dfrac{1}{p}\right)\left(1 - \dfrac{1}{q}\right)\left(1 - \dfrac{1}{r}\right) を展開した式と同じ。
p^a \cdot \dfrac{p - 1}{p} = p^{a-1}(p - 1) で、q、r も同じように変形できるから、示すべき等式が成り立ちます。
図は p = 2、q = 3、r = 5、a = 2、b = c = 1 の N = 60 で、最後に残る 16 個が 60 と互いに素な数。
2 \cdot 3 \cdot 5 \cdot 7 = 210 が 100 を超えるため、100 以下の n の素因数は 3 個以下。素因数が 1 個、2 個のときも、(1) と同じ数え方ができる。
n の相異なる素因数を p_1, \cdots, p_k とすると、f(n) = n\left(1 - \dfrac{1}{p_1}\right) \cdots \left(1 - \dfrac{1}{p_k}\right) だから、次の式が成り立ちます。
\dfrac{n}{f(n)} = \dfrac{p_1}{p_1 - 1} \cdots \dfrac{p_k}{p_k - 1}
f(n) が n の約数になるのは、この値が整数のとき。分母の (p_1 - 1) \cdots (p_k - 1) が、分子の p_1 \cdots p_k を割り切るときです。
図は 5 \leqq n \leqq 100 での \dfrac{n}{f(n)} の値で、整数になるのは 2 と 3 の高さの点だけ。
奇数の素因数 p があると p - 1 は偶数で、分母が偶数になる。分子も偶数でなければ割り切れず、2 が素因数に含まれます。
奇数の素因数が 2 つあると、分母は 4 で割り切れる。分子は 2 を 1 つしか含まないため、割り切れない。
よって素因数は 2 だけか、2 と奇数の素数 q の 2 つです。2 だけなら \dfrac{n}{f(n)} = 2 で、条件を満たす。
2 と q のときは \dfrac{n}{f(n)} = \dfrac{2q}{q - 1}。q - 1 と q は互いに素だから q - 1 は 2 の約数で、q = 3 に限られる。値は 3 になります。
n = 2^e (e \geqq 1) または n = 2^e3^c (e \geqq 1,\ c \geqq 1) のうち、5 \leqq n \leqq 100 のものを並べる。
2^e は 8、16、32、64。3 の指数が 1 のものは 6、12、24、48、96 です。
指数が 2 のものは 18、36、72、3 のものは 54。指数が 4 だと 2 \cdot 3^4 = 162 で、100 を超える。
答えは 6、8、12、16、18、24、32、36、48、54、64、72、96 の 13 個です。