トップ› 大阪大学› 2003年› 文系第2問

大阪大学 2003年文系第2問解説

方針・初手

$f(m)$ は自然数 $m$ の「相異なる素因数の積」を表す関数である。つまり、$m$ を素因数分解したときに現れる素数たちを1回ずつ掛け合わせた値である。

(1) では、両辺を素因数分解したときの「任意の素数 $p$ の指数」を比較することで証明する。最大公約数 $d$ や積 $mn$ における素数 $p$ の指数がどのように振る舞うかを丁寧に追うのが確実である。

(2) は、(1) で示した等式 $f(d)f(mn) = f(m)f(n)$ を活用する。これにより、考えるべき方程式から $f(mn)$ を消去でき、最大公約数 $d$ に関する条件に帰着させて数え上げることができる。

解法1

(1)

任意の自然数 $x$ と素数 $p$ に対して、$x$ が $p$ で割り切れる回数（指数）を $v_p(x)$ と表す。 $f(x)$ の定義より、$x$ の素因数の指数はすべて $1$ になるため、

$$ v_p(f(x)) = \begin{cases} 1 & (v_p(x) \ge 1 \text{ のとき}) \\ 0 & (v_p(x) = 0 \text{ のとき}) \end{cases} $$

が成り立つ。（$x=1$ のときはすべての $p$ について $v_p(1)=0$ となり上式に含まれる）

$d$ は $m, n$ の最大公約数であるから、任意の素数 $p$ について

$$ v_p(d) = \min(v_p(m), v_p(n)) $$

また、積 $mn$ については

$$ v_p(mn) = v_p(m) + v_p(n) $$

である。ここで、任意の素数 $p$ について $v_p(m)$ と $v_p(n)$ の値で場合分けを行う。

(i)

$v_p(m) \ge 1$ かつ $v_p(n) \ge 1$ のとき $v_p(d) \ge 1$、$v_p(mn) \ge 2$ となる。したがって、$f(m), f(n), f(d), f(mn)$ はすべて $p$ でちょうど $1$ 回ずつ割り切れるので、左辺について $v_p(f(d)f(mn)) = 1 + 1 = 2$ 右辺について $v_p(f(m)f(n)) = 1 + 1 = 2$ ゆえに、左辺と右辺の $p$ の指数は等しい。

(ii)

$v_p(m) \ge 1$ かつ $v_p(n) = 0$ のとき $v_p(d) = 0$、$v_p(mn) \ge 1$ となる。したがって、$f(m), f(mn)$ は $p$ でちょうど $1$ 回割り切れ、$f(n), f(d)$ は $p$ で割り切れないので、左辺について $v_p(f(d)f(mn)) = 0 + 1 = 1$ 右辺について $v_p(f(m)f(n)) = 1 + 0 = 1$ ゆえに、左辺と右辺の $p$ の指数は等しい。

(iii)

$v_p(m) = 0$ かつ $v_p(n) \ge 1$ のとき対称性より、（ii）と同様に左辺と右辺の $p$ の指数は等しい。

(iv)

$v_p(m) = 0$ かつ $v_p(n) = 0$ のとき $v_p(d) = 0$、$v_p(mn) = 0$ となる。したがって、$f(m), f(n), f(d), f(mn)$ はいずれも $p$ で割り切れないので、左辺について $v_p(f(d)f(mn)) = 0 + 0 = 0$ 右辺について $v_p(f(m)f(n)) = 0 + 0 = 0$ ゆえに、左辺と右辺の $p$ の指数は等しい。

以上より、すべての素数 $p$ について、左辺 $f(d)f(mn)$ と右辺 $f(m)f(n)$ の素因数分解における各素数の指数が完全に一致するため、

$$ f(d)f(mn) = f(m)f(n) $$

が成り立つ。（証明終）

(2)

(1) の結果より、$f(mn) = \frac{f(m)f(n)}{f(d)}$ である。

全事象は $m, n \in \{1, 2, \dots, 10\}$ より $10 \times 10 = 100$ 通りである。

確率 $p_1$ について： $f(mn) = f(m)f(n)$ に (1) の結果を代入すると

$$ \frac{f(m)f(n)}{f(d)} = f(m)f(n) $$

$f(m) \ge 1, f(n) \ge 1$ より割ることができ、$f(d) = 1$ を得る。自然数 $d$ について $f(d) = 1$ となるのは $d = 1$ のとき、すなわち $m$ と $n$ が互いに素となるときである。各 $m$ に対して互いに素となる $n$ の個数を数える。

$m = 1$ のとき： $n$ は $1$ から $10$ の $10$ 通り
$m = 2, 4, 8$ のとき： $n$ は奇数の $5$ 通り。計 $3 \times 5 = 15$ 通り
$m = 3, 9$ のとき： $n$ は $3$ の倍数以外の $7$ 通り。計 $2 \times 7 = 14$ 通り
$m = 5$ のとき： $n$ は $5$ の倍数以外の $8$ 通り
$m = 6$ のとき： $n$ は $2$ の倍数でも $3$ の倍数でもない $\{1, 5, 7\}$ の $3$ 通り
$m = 7$ のとき： $n$ は $7$ の倍数以外の $9$ 通り
$m = 10$ のとき： $n$ は $2$ の倍数でも $5$ の倍数でもない $\{1, 3, 7, 9\}$ の $4$ 通り

合計すると $10 + 15 + 14 + 8 + 3 + 9 + 4 = 63$ 通りとなる。よって、

$$ p_1 = \frac{63}{100} $$

確率 $p_2$ について：同様に $2f(mn) = f(m)f(n)$ へ代入して整理すると

$$ f(d) = 2 $$

自然数 $d$ について $f(d) = 2$ となるのは、$d$ が素因数として $2$ のみをもつときである。 $m, n \le 10$ より最大公約数 $d \le 10$ であるから、$d = 2, 4, 8$ のいずれかである。

(ア)

$d = 8$ のとき $m, n$ はともに $8$ の倍数であり、条件を満たすのは $(m, n) = (8, 8)$ の $1$ 通り。

(イ)

$d = 4$ のとき $m, n$ はともに $4$ の倍数であり、該当する数は $4, 8$。 $(m, n) = (4, 4), (4, 8), (8, 4)$ のいずれも最大公約数は $4$ となるため、適する組は $3$ 通り。

(ウ)

$d = 2$ のとき $m, n$ はともに $2$ の倍数。該当する数は $2, 4, 6, 8, 10$。最大公約数が $2$ となるため、$m = 2x, n = 2y$ とおくと、$x, y \in \{1, 2, 3, 4, 5\}$ であり、かつ $x, y$ が互いに素となればよい。

$x = 1$ のとき： $y \in \{1, 2, 3, 4, 5\}$ の $5$ 通り
$x = 2, 4$ のとき： $y$ は奇数の $3$ 通り。計 $2 \times 3 = 6$ 通り
$x = 3$ のとき： $y \in \{1, 2, 4, 5\}$ の $4$ 通り
$x = 5$ のとき： $y \in \{1, 2, 3, 4\}$ の $4$ 通り

これらは計 $19$ 通り。

以上から、$f(d) = 2$ となる $(m, n)$ の組は $1 + 3 + 19 = 23$ 通りである。よって、

$$ p_2 = \frac{23}{100} $$

解説

(1) は自然数の性質に関する抽象的な証明であるが、「任意の素数 $p$ で何回割り切れるか（$p$ 進付値）」に持ち込むと機械的に処理できる。最大公約数の $p$ の指数が $\min$ で表される性質は整数問題で頻出である。 (2) は (1) の結果を最大限利用する誘導になっている。(1)の等式を方程式に代入すると、$f(d)$ の値のみが決定されるため、最大公約数に関する条件に還元される。あとは漏れなく重複なく数え上げるだけの標準的な確率問題となる。