トップ› 大阪大学› 2024年› 理系第5問

大阪大学 2024年理系第5問解説

方針・初手

(1) では、全体集合から $p, q, r$ の倍数となるものを除くという、包含排斥の原理を用いた典型的なアプローチをとる。 (2) では、(1) で得られた式（オイラーのトーティエント関数）の形から、$f(n)$ が $n$ の約数となる条件を立式する。$n$ の素因数の個数で場合分けを行い、条件を満たす素数を絞り込む。

解法1

(1)

$N = p^a q^b r^c$ とおく。自然数 $1, 2, 3, \cdots, N$ 全体の集合を $U$ とする。また、$U$ の要素のうち、$p$ の倍数、$q$ の倍数、$r$ の倍数全体の集合をそれぞれ $A, B, C$ とおく。各集合の要素の個数は次のようになる。

$$ \begin{aligned} n(U) &= p^a q^b r^c \\ n(A) &= \frac{N}{p} = p^{a-1} q^b r^c \\ n(B) &= \frac{N}{q} = p^a q^{b-1} r^c \\ n(C) &= \frac{N}{r} = p^a q^b r^{c-1} \\ n(A \cap B) &= \frac{N}{pq} = p^{a-1} q^{b-1} r^c \\ n(B \cap C) &= \frac{N}{qr} = p^a q^{b-1} r^{c-1} \\ n(C \cap A) &= \frac{N}{rp} = p^{a-1} q^b r^{c-1} \\ n(A \cap B \cap C) &= \frac{N}{pqr} = p^{a-1} q^{b-1} r^{c-1} \end{aligned} $$

$N$ と互いに素であるものは、$p, q, r$ のいずれの倍数でもない自然数である。したがって、求める個数 $f(N)$ は、包含排斥の原理により次のように計算できる。

$$ \begin{aligned} f(p^a q^b r^c) &= n(U) - n(A) - n(B) - n(C) + n(A \cap B) + n(B \cap C) + n(C \cap A) - n(A \cap B \cap C) \\ &= p^a q^b r^c - p^{a-1} q^b r^c - p^a q^{b-1} r^c - p^a q^b r^{c-1} + p^{a-1} q^{b-1} r^c + p^a q^{b-1} r^{c-1} + p^{a-1} q^b r^{c-1} - p^{a-1} q^{b-1} r^{c-1} \\ &= p^{a-1} q^{b-1} r^{c-1} \left( pqr - qr - pr - pq + r + p + q - 1 \right) \\ &= p^{a-1} q^{b-1} r^{c-1} (p-1)(q-1)(r-1) \end{aligned} $$

よって、等式が成り立つことが示された。

(2)

(1) と同様の包含排斥の原理による議論から、自然数 $n$ が互いに異なる素因数 $p_1, p_2, \cdots, p_k$ を持ち、$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ （$a_i$ は自然数）と素因数分解されるとき、$f(n)$ は次のように表される。

$$ f(n) = p_1^{a_1-1} p_2^{a_2-1} \cdots p_k^{a_k-1} (p_1-1)(p_2-1) \cdots (p_k-1) $$

$f(n)$ が $n$ の約数となる条件は、$\frac{n}{f(n)}$ が整数となることである。ここで、

$$ \frac{n}{f(n)} = \frac{p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}}{p_1^{a_1-1} p_2^{a_2-1} \cdots p_k^{a_k-1} (p_1-1)(p_2-1) \cdots (p_k-1)} = \frac{p_1 p_2 \cdots p_k}{(p_1-1)(p_2-1) \cdots (p_k-1)} $$

この値が整数となる条件を、素因数の種類数 $k$ によって場合分けして調べる。ここで $p_1 < p_2 < \cdots < p_k$ とする。

(i)

$k=1$ のとき $n = p_1^{a_1}$ であり、

$$ \frac{n}{f(n)} = \frac{p_1}{p_1-1} $$

となる。これが整数となるためには、$p_1-1$ が $p_1$ の約数である必要がある。$p_1-1$ と $p_1$ は互いに素な連続する整数であるため、$p_1-1 = 1$ のみが適する。よって、$p_1 = 2$ となり、$n = 2^{a_1}$ である。 $5 \le n \le 100$ を満たすのは、$2^3, 2^4, 2^5, 2^6$ のいずれかであるため、 $n = 8, 16, 32, 64$

(ii)

$k=2$ のとき $n = p_1^{a_1} p_2^{a_2}$ であり、

$$ \frac{n}{f(n)} = \frac{p_1 p_2}{(p_1-1)(p_2-1)} $$

となる。もし $p_1 \ge 3$ とすると、$p_1, p_2$ はいずれも奇素数となる。このとき $p_1-1, p_2-1$ はいずれも偶数となるため、分母は偶数（$4$ の倍数）となる。一方、分子 $p_1 p_2$ は奇数となるため、この分数が整数になることはない。したがって、$p_1 = 2$ でなければならない。このとき、

$$ \frac{n}{f(n)} = \frac{2 p_2}{p_2-1} $$

となる。$p_2-1$ と $p_2$ は互いに素であるため、これが整数となるには $p_2-1$ が $2$ の約数である必要がある。よって $p_2-1 = 1, 2$ すなわち $p_2 = 2, 3$ となるが、$p_2 > p_1 = 2$ より $p_2 = 3$ である。したがって、$n = 2^{a_1} 3^{a_2}$ となる。 $5 \le 2^{a_1} 3^{a_2} \le 100$ を満たす自然数 $a_1, a_2$ の組を調べる。

$a_2 = 1$ のとき $n = 3 \cdot 2^{a_1}$ となり、$a_1 = 1, 2, 3, 4, 5$ が適する。$n = 6, 12, 24, 48, 96$
$a_2 = 2$ のとき $n = 9 \cdot 2^{a_1}$ となり、$a_1 = 1, 2, 3$ が適する。$n = 18, 36, 72$
$a_2 = 3$ のとき $n = 27 \cdot 2^{a_1}$ となり、$a_1 = 1$ が適する。$n = 54$
$a_2 \ge 4$ のとき $n = 3^{a_2} \cdot 2^{a_1} \ge 81 \cdot 2 = 162$ となり不適。

(iii)

$k \ge 3$ のとき

$$ \frac{n}{f(n)} = \frac{p_1 p_2 \cdots p_k}{(p_1-1)(p_2-1) \cdots (p_k-1)} $$

において、$p_1 = 2$ と仮定しても、分子が持つ素因数 $2$ の個数は $1$ 個であるのに対し、分母には偶数となる因子 $(p_2-1), \dots, (p_k-1)$ が少なくとも $2$ 個含まれるため、分母の方が素因数 $2$ を多く持つ。したがって、この分数が整数になることはない。

以上（i）〜（iii）より、求める自然数 $n$ は出揃った。

解説

オイラーのトーティエント関数と呼ばれる $\varphi(n)$ の性質を誘導形式で証明し、利用させる問題である。 (1) では素因数が $3$ 種類の場合を証明させているが、証明の考え方自体は $k$ 種類に一般化可能であり、(2) ではそれを自明なものとして用いてよい。(2) では「整数になる条件」を考える際、分母と分子の偶奇（素因数 $2$ の個数）に注目することが重要なポイントとなる。互いに素である性質と合わせて、素因数 $p=2, 3$ しかあり得ないことを論理的に絞り込む過程が求められる。