トップ› 京都大学› 2020年› 理系第4問

京都大学 2020年理系第4問解説

方針・初手

関数 $B(a)$ は「整数 $a$ が $3$ で何回割り切れるか（素因数分解したときの $3$ の指数）」を表します。$A(m,n)$ の最大値を求めるため、$f(m,n)$ が $3$ でなるべく多く割り切れるような $(m, n)$ を探します。このような問題では、合同式を用いて $\pmod 3$、$\pmod 9$、$\pmod{27}$ $\cdots$ と段階的に $m, n$ の条件を絞り込んでいくアプローチが有効です。

解法1

$f(m,n) = m^3 + n^2 + n + 3 = m^3 + n(n+1) + 3$

$A(m,n) \geqq 1$ となるためには、少なくとも $f(m,n) \equiv 0 \pmod 3$ でなければならない。条件 (iii) より $n$ は $3$ で割り切れないので、$n \equiv 1, 2 \pmod 3$ のいずれかである。

[1] $n \equiv 1 \pmod 3$ のとき

$n(n+1) \equiv 1 \cdot 2 \equiv 2 \pmod 3$ であるから $f(m,n) \equiv m^3 + 2 + 0 \equiv m^3 + 2 \pmod 3$ $f(m,n) \equiv 0 \pmod 3$ となるためには $m^3 \equiv 1 \pmod 3$、すなわち $m \equiv 1 \pmod 3$ が必要である。ここで、$k, l$ を整数として $m = 3k+1, n = 3l+1$ とおく。

$$ f(m,n) = (3k+1)^3 + (3l+1)^2 + (3l+1) + 3 $$

$$ = (27k^3 + 27k^2 + 9k + 1) + (9l^2 + 6l + 1) + (3l + 1) + 3 $$

$$ = 27k^3 + 27k^2 + 9k + 9l^2 + 9l + 6 $$

$$ = 9(3k^3 + 3k^2 + k + l^2 + l) + 6 $$

よって、$f(m,n) \equiv 6 \pmod 9$ となり、$f(m,n)$ は $3$ で割り切れるが $9$ では割り切れない。したがって、この場合 $A(m,n) = 1$ となる。

[2] $n \equiv 2 \pmod 3$ のとき

$n(n+1) \equiv 2 \cdot 3 \equiv 0 \pmod 3$ であるから $f(m,n) \equiv m^3 + 0 + 0 \equiv m^3 \pmod 3$ $f(m,n) \equiv 0 \pmod 3$ となるためには $m \equiv 0 \pmod 3$ が必要である。 $k, l$ を整数として $m = 3k, n = 3l+2$ とおく。

$$ f(m,n) = (3k)^3 + (3l+2)^2 + (3l+2) + 3 $$

$$ = 27k^3 + 9l^2 + 12l + 4 + 3l + 5 $$

$$ = 27k^3 + 9l^2 + 15l + 9 $$

この値がさらに $9$ で割り切れる（$A(m,n) \geqq 2$ となる）ためには $15l \equiv 0 \pmod 9 \iff 3l \equiv 0 \pmod 9 \iff l \equiv 0 \pmod 3$ が必要である。 $j$ を整数として $l = 3j$ とおくと、$n = 3(3j)+2 = 9j+2$ となる。これを代入すると

$$ f(m,n) = 27k^3 + 9(3j)^2 + 15(3j) + 9 = 27k^3 + 81j^2 + 45j + 9 $$

$$ = 9(3k^3 + 9j^2 + 5j + 1) $$

この値がさらに $27$ で割り切れる（$A(m,n) \geqq 3$ となる）ためには、括弧内が $3$ の倍数であればよい。 $3k^3 + 9j^2 + 5j + 1 \equiv 5j + 1 \equiv 2j + 1 \pmod 3$ より $2j + 1 \equiv 0 \pmod 3 \iff 2j \equiv 2 \pmod 3 \iff j \equiv 1 \pmod 3$ が必要である。 $i$ を整数として $j = 3i+1$ とおくと、$n = 9(3i+1)+2 = 27i+11$ となる。条件 (ii) $1 \leqq n \leqq 30$ を満たすのは $i = 0$、すなわち $n = 11$ のときのみである。

$n = 11$ のとき

$$ f(m, 11) = m^3 + 11^2 + 11 + 3 = m^3 + 135 $$

$m = 3k$ であったから

$$ f(m, 11) = 27k^3 + 135 = 27(k^3 + 5) $$

この値がさらに $81$ で割り切れる（$A(m,n) \geqq 4$ となる）ためには、$k^3 + 5$ が $3$ で割り切れる必要がある。 $k^3 + 5 \equiv k^3 + 2 \pmod 3$ より、$k^3 \equiv 1 \pmod 3 \iff k \equiv 1 \pmod 3$。 $h$ を（非負）整数として $k = 3h+1$ とおくと、

$$ k^3 + 5 = (3h+1)^3 + 5 = 27h^3 + 27h^2 + 9h + 6 $$

$$ = 3(9h^3 + 9h^2 + 3h + 2) $$

ここで、括弧内の式について

$$ 9h^3 + 9h^2 + 3h + 2 \equiv 2 \pmod 3 $$

となるため、括弧内は $3$ で割り切れない。したがって、$k^3 + 5$ は $3$ でちょうど $1$ 回だけ割り切れる。ゆえに、$f(m,11) = 27 \times 3 \times (\text{3で割り切れない整数}) = 81 \times (\text{3で割り切れない整数})$ となり、$f(m,11)$ は $81=3^4$ で割り切れるが $243=3^5$ では割り切れない。以上より、$A(m,n)$ の最大値は $4$ である。

最大値をとるときの $m$ は、$m = 3k = 3(3h+1) = 9h+3$ と表せる。条件 (i) $1 \leqq m \leqq 30$ を満たす $h$ は $h = 0, 1, 2, 3$ であり、それぞれ $m = 3, 12, 21, 30$ となる。

解説

整数問題において「ある数 $N$ が素数 $p$ で最大何回割り切れるか」を問う問題では、合同式を用いて法を $p, p^2, p^3, \dots$ と大きくしながら条件を絞り込んでいく手法が極めて有効です。本問でも $\pmod 3 \to \pmod 9 \to \pmod{27}$ と順に調べることで、変数 $n$ の形が完全に $n=11$ へと確定し、その後の $m$ の探索も容易になります。場合分けの各ステップで「これ以上は $3$ で割れない」ことを論理的に示し切る記述力が求められます。