大阪大学 2024年度理系数学第5問解答・解説

問題

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

(1) 自然数 $a, b, c$ および相異なる素数 $p, q, r$ に対して，等式

f (p^{a} q^{b} r^{c}) = p^{a - 1} q^{b - 1} r^{c - 1} (p - 1) (q - 1) (r - 1)

が成り立つことを示せ．

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

出典：大阪大学 2024年度前期日程第2次学力試験理系第5問

方針

(1) は $p, q, r$ のいずれでも割り切れない数を数えればよいので，包除原理で $N (1 - 1/ p) (1 - 1/ q) (1 - 1/ r)$ と因数分解する。(2) では一般の $n$ について，相異なる素因数の集合だけで $n / f (n) = \prod p / (p - 1)$ が決まることを使う。 $f (n)$ が $n$ の約数である条件はこの比が整数であること。 $100$ 以下という制約から，素因数集合が ${2}$ または ${2, 3}$ に限られることを示し，最後に指数を列挙する。

解答

(1)

$N = p^{a} q^{b} r^{c}$ とおく。 $1, 2, \dots, N$ のうち， $N$ と互いに素であるものは， $p, q, r$ のいずれでも割り切れない数である。

包除原理を用いると，その個数は

N - \frac{N}{p} - \frac{N}{q} - \frac{N}{r} + \frac{N}{pq} + \frac{N}{p r} + \frac{N}{q r} - \frac{N}{pq r}

である。これは $N (1 - \frac{1}{p}) (1 - \frac{1}{q}) (1 - \frac{1}{r})$ に等しい。したがって

f (p^{a} q^{b} r^{c}) = p^{a} q^{b} r^{c} \cdot \frac{p - 1}{p} \cdot \frac{q - 1}{q} \cdot \frac{r - 1}{r}

であり， $f (p^{a} q^{b} r^{c}) = p^{a - 1} q^{b - 1} r^{c - 1} (p - 1) (q - 1) (r - 1)$ が成り立つ。

(2)

$n$ の相異なる素因数を $p_{1}, p_{2}, \dots, p_{k}$ とする。(1)と同じ包除原理により $f (n) = n \prod_{j = 1}^{k} (1 - \frac{1}{p _{j}})$ である。したがって $\frac{n}{f ( n )} = \prod_{j = 1}^{k} \frac{p _{j}}{p _{j} - 1}$ である。 $f (n)$ が $n$ の約数であることは，この $n / f (n)$ が整数であることと同値である。

まず， $2$ が $n$ の素因数でないとする。このとき各 $p_{j}$ は奇素数なので，分子 $\prod p_{j}$ は奇数である。一方，分母 $\prod (p_{j} - 1)$ は偶数を因数にもつ。よって約分しても分母に $2$ の因数が残り， $n / f (n)$ は整数にならない。したがって $2$ は必ず素因数に含まれる。

次に， $2$ は含むが $3$ は含まない場合を考える。素因数が $2$ だけならよい。もし $5$ 以上の奇素数を含むなら， $n ≦ 100$ のもとで $2$ とともに入れられる奇素数の集合について $2 < \frac{n}{f ( n )} < 3$ となる。実際，奇素数が1個なら $2 p / (p - 1) < 5/2$ であり，2個以上なら最も比を大きくする $5, 7$ を入れても $2 \cdot \frac{5}{4} \cdot \frac{7}{6} = \frac{35}{12} < 3$ である。よってこの場合 $n / f (n)$ は整数にならない。したがって， $3$ を含まないなら素因数集合は ${2}$ に限られる。

最後に， $2$ と $3$ を含む場合を考える。 $5$ 以上の素因数をさらに2個含めると，最小でも $2 \cdot 3 \cdot 5 \cdot 7 = 210 > 100$ となるので，追加できる素因数は高々1個である。追加素因数を $p ≧ 5$ とすると $\frac{n}{f ( n )} = 2 \cdot \frac{3}{2} \cdot \frac{p}{p - 1} = \frac{3 p}{p - 1}$ であり， $3 < \frac{3 p}{p - 1} ≦ \frac{15}{4} < 4$ だから整数にならない。したがって，この場合の素因数集合は ${2, 3}$ に限られる。

以上より，条件を満たす $n$ は $n = 2^{a}$ または $n = 2^{a} 3^{b} (a ≧ 1, b ≧ 1)$ の形に限られる。逆にこれらの形では $\frac{n}{f ( n )} = 2 または 3$ となるので，確かに $f (n)$ は $n$ の約数である。 $5 ≦ n ≦ 100$ を満たすものを列挙する。 $2^{a}$ 型からは $8, 16, 32, 64$ を得る。 $2^{a} 3^{b}$ 型からは $6, 12, 18, 24, 36, 48, 54, 72, 96$ を得る。したがって求める自然数は $6, 8, 12, 16, 18, 24, 32, 36, 48, 54, 64, 72, 96$ である。

大阪大学 2024年度理系数学 第5問

問題

方針

解答

(1)

(2)

大阪大学 2024年度
理系数学第5問