2026年 東京大学理系入試問題のフカヨミ｜メビオ数学科 亀井

$n$ を正の整数とする.$n$ の正の約数のうち,3で割って1余るものの個数を $f(n)$ ,3で割って2余るものの個数を $g(n)$ とする.$f(n) \geqq g(n)$ を示せ.

解答を示します.（「です,ます調はしばらく休みます.」）

以下では合同式の法はすべて3とする.すべての素数を次の3つの集合に分類する.

• $P_0=\{3\}$
• $P_1=\{p \text{ 素数 } | \ p \equiv 1\}$
• $P_2=\{p \text{ 素数 } | \ p \equiv 2\}$

また,自然数 $n$ に対して $Q(n)=\{n \text{ の素因数}\}$ と定める.（ $Q(1)=\emptyset$ である.）

すべての自然数 $n$ に対する $f(n) \geqq g(n)$ の成立を数学的帰納法（完全帰納法）で証明する.

• (i) $f(1)=1, \ g(1)=0,$ $f(2)=1, \ g(2)=1,$ $f(3)=1, \ g(3)=0$
  より $n \leqq 3$ の場合 $f(n) \geqq g(n)$ は成り立っている.

• (ii) $n$ を4以上のある自然数として $1 \leqq k \leqq n-1$ における $f(k) \geqq g(k)$ の成立を仮定する. $f(n) \geqq g(n)$ の成立を示したい．

  (a) $Q(n) \cap P_2 = \emptyset$ の場合, $g(n)=0$ だから $f(n) \geqq g(n)$ は成り立つ.

  (b) $Q(n) \cap P_2 \ne \emptyset$ の場合, $p \in Q(n) \cap P_2$ として $n=p^m \cdot n_1$ （ $m \geqq 1$ , $p$ と $n_1$ は互いに素）とおく. $n_1 < n$ だから帰納法の仮定により $f(n_1) \geqq g(n_1)$ は成り立っている.

  $p^j$ を $p^m$ の約数, $b$ を $n_1$ の約数として, $n=p^m \cdot n_1$ の約数 $p^j \cdot b$ について考える.

  (b1) $m=2l$ の場合

  $$ p^j\cdot b \equiv 1 \iff (b \equiv 1\ \text{かつ}\ j=0, 2, \dots, 2l) $$

  $$ \text{または}\ (b \equiv 2\ \text{かつ}\ j=1, 3, \dots, 2l-1) $$

  $$ p^j\cdot b \equiv 2 \iff (b \equiv 2\ \text{かつ}\ j=0, 2, \dots, 2l) $$

  $$ \text{または}\ (b \equiv 1\ \text{かつ}\ j=1, 3, \dots, 2l-1) $$

  $j=0, 2, \dots, 2l$ は $l+1$ 個であり, $j=1, 3, \dots, 2l-1$ は $l$ 個であるから $f(n)=(l+1)f(n_1)+lg(n_1)$ , $g(n)=(l+1)g(n_1)+lf(n_1)$ となり,

  $$ f(n)-g(n) = \{(l+1)f(n_1)+lg(n_1)\} - \{(l+1)g(n_1)+lf(n_1)\} $$

  $$ = f(n_1)-g(n_1) \geqq 0 $$

  (b2) $m=2l-1$ の場合

  $$ p^j\cdot b \equiv 1 \iff (b \equiv 1\ \text{かつ}\ j=0, 2, \dots, 2l-2) $$

  $$ \text{または}\ (b \equiv 2\ \text{かつ}\ j=1, 3, \dots, 2l-1) $$

  $$ p^j\cdot b \equiv 2 \iff (b \equiv 2\ \text{かつ}\ j=0, 2, \dots, 2l-2) $$

  $$ \text{または}\ (b \equiv 1\ \text{かつ}\ j=1, 3, \dots, 2l-1) $$

  $j=0, 2, \dots, 2l-2$ は $l$ 個であり, $j=1, 3, \dots, 2l-1$ は $l$ 個であるから $f(n)=lf(n_1)+lg(n_1)$ , $g(n)=lg(n_1)+lf(n_1)$ となり,

  $$ \begin{aligned} f(n)-g(n) = \{lf(n_1)+lg(n_1)\} - \{lg(n_1)+lf(n_1)\} = 0 \end{aligned} $$

  (b1), (b2) のどちらの場合も $f(n) \geqq g(n)$ は成立する.

以上，数学的帰納法によって証明された.（証明終）

$g(n)=15$ であるとき， $f(n)$ がとりうる値を求めよ．