東京大学 理系 2026年度 第6問 解説
問題編
問題
$n$ を正の整数とする。 $n$ の正の約数のうち、 $3$ で割って $1$ 余るものの個数を $f(n)$、 $3$ で割って $2$ 余るものの個数を $g(n)$ とする。
(1) $f(2800),g(2800)$ を求めよ。
(2) $f(n)\geqq g(n)$ を示せ。
(3) $g(n)=15$ であるとき、 $f(n)$ のとりうる値を求めよ。
考え方
(1)で具体的に書き出してみると、答えは出ますが(2)以降につながりません。(1)を計算で出すようにするにはどうすればいいかを考えます。
(2)をスッキリ書くのは難しいです。数学的帰納法を使って書くにしても、量がかなり多くなってしまいます。
(3)は、(2)での計算をよく見ればイメージはつくかもしれませんが、ちゃんと説明するのは大変です。また、候補がわかったとしても、本当にその値をとることがあるのかは、調べる必要があります。
時間内で解くのは、難しすぎます。
解答編
問題
$n$ を正の整数とする。 $n$ の正の約数のうち、 $3$ で割って $1$ 余るものの個数を $f(n)$、 $3$ で割って $2$ 余るものの個数を $g(n)$ とする。
(1) $f(2800),g(2800)$ を求めよ。
解答
(1)
$2800=2^4\cdot 5^2\cdot 7$ なので、正の約数は以下の形で書ける。\[ 2^a\cdot 5^b\cdot 7^c \]ただし、 $a,b,c$ は $0$ 以上の整数で、 $a\leqq 4,b\leqq 2,c\leqq 1$ である。
このとき、$\mod 3$ で考えると $2,5,7$ は、それぞれ $-1,-1,1$ と同値なので、
\begin{eqnarray}
2^a\cdot 5^b\cdot 7^c
& \equiv &
(-1)^a\cdot (-1)^b\cdot 1^c \\[5pt]
& \equiv &
(-1)^{a+b+2c}
\end{eqnarray}とかける。
これより、 $3$ で割って $1$ 余る正の約数となるのは、
・「$a$ が偶数、 $b$ が偶数、 $c$ は何でもいい」
・「$a$ が奇数、 $b$ が奇数、 $c$ は何でもいい」
のときなので
\begin{eqnarray}
f(n)=(3\cdot 2+2\cdot 1)\cdot2=16
\end{eqnarray}となる。一方、 $3$ で割って $2$ 余る正の約数となるのは、
・「$a$ が偶数、 $b$ が奇数、 $c$ は何でもいい」
・「$a$ が奇数、 $b$ が偶数、 $c$ は何でもいい」
のときなので
\begin{eqnarray}
g(n)=(3\cdot 1+2\cdot 2)\cdot2=14
\end{eqnarray}となる。
よって、 $f(n)=16,g(n)=14$ …（答）
解答編 つづき
問題
(2) $f(n)\geqq g(n)$ を示せ。
解答
(2)
まず、 $f(1)=1,g(1)=0$ なので、 $f(1)\geqq g(1)$ が成り立つ。
以下では、 $n\geqq 2$ とする。
一般に、正の整数 $n$ は以下のように書ける。\[ n=3^{c} \cdot p_1^{a_1} \cdot p_2^{a_2} \cdots p_m^{a_m} \]ここで、 $c$ は $0$ 以上の整数、 $a_1,\cdots,a_m$ は正の整数、 $p_1,\cdots,p_m$ は相異なる素数で、 $3$ とも異なるものである。この $m$ についての数学的帰納法で示す。
(i)
$m=1$ のとき、 $n=3^c p_1^{a_1}$ と書けていたとする。
$\bmod 3$ で $p_1\equiv 1$ ならば、 $p_1^k\equiv 1$ なので、 $f(n)=a_1+1, g(n)=0$ である。
$p_1\equiv -1$ ならば、 $p_1^k\equiv (-1)^k$ なので、 $a_1$ が奇数なら\[ f(n)=g(n)=\dfrac{a_1 +1}{2} \]となり、 $a_1$ が偶数なら\[ f(n)=\dfrac{a_1}{2}+1,\ g(n)=\dfrac{a_1}{2} \]となる。
よって、いずれの場合も $f(n)\geqq g(n)$ が成り立つ。
(ii)
$m=k$ のとき、\[ f(3^{c} \cdot p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}) \geqq g(3^{c} \cdot p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}) \]が、$3$ 以外の任意の素数 $p_1,\cdots,p_k$、正の整数 $a_1,\cdots,a_k$、非負整数 $c$ に対して成り立つとする。
$m=k+1$ のとき、\[ 3^{c} \cdot p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k} p_{k+1}^{a_{k+1}} \]と書けていたとする。ここで、\[ N=3^{c} \cdot p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k} \]とおくと、仮定より、 $f(N)\geqq g(N)$ が成り立つ。
$p_{k+1} \equiv 1$ なら、
\begin{eqnarray}
f(N p_{k+1}^{a_{k+1}}) &=& (a_{k+1}+1) f(N) \\[5pt]
g(N p_{k+1}^{a_{k+1}}) &=& (a_{k+1}+1) g(N) \\[5pt]
\end{eqnarray}なので、仮定より、 $f(N p_{k+1}^{a_{k+1}})\geqq g(N p_{k+1}^{a_{k+1}})$ が成り立つ。
$p_{k+1} \equiv -1$ なら、 $a_{k+1}$ が奇数なら、$1$ 余るもの同士、 $2$ 余るもの同士を掛けると、それぞれ $1$ 余るものができることなどから、
\begin{eqnarray}
f(N p_{k+1}^{a_{k+1}}) &=& \frac{a_{k+1}+1}{2} (f(N)+g(N)) \\[5pt]
g(N p_{k+1}^{a_{k+1}}) &=& \frac{a_{k+1}+1}{2} (f(N)+g(N)) \\[5pt]
\end{eqnarray}なので、$f(N p_{k+1}^{a_{k+1}})\geqq g(N p_{k+1}^{a_{k+1}})$ が成り立つ。
$a_{k+1}$ が偶数なら、
\begin{eqnarray}
f(N p_{k+1}^{a_{k+1}}) &=& \left(\frac{a_{k+1}}{2}+1\right) f(N) +\frac{a_{k+1}}{2}g(N) \\[5pt]
g(N p_{k+1}^{a_{k+1}}) &=& \frac{a_{k+1}}{2} f(N) +\left(\frac{a_{k+1}}{2}+1\right)g(N) \\[5pt]
\end{eqnarray}となる。このとき
\begin{eqnarray}
& &
f(N p_{k+1}^{a_{k+1}})-g(N p_{k+1}^{a_{k+1}}) \\[5pt]
&=&
f(N) -g(N) \\[5pt]
\end{eqnarray}なので、仮定より、$f(N p_{k+1}^{a_{k+1}})\geqq g(N p_{k+1}^{a_{k+1}})$ が成り立つ。
以上から、いずれのケースでも、 $f(N p_{k+1}^{a_{k+1}})\geqq g(N p_{k+1}^{a_{k+1}})$ が成り立つので、 $m=k+1$ の時も成り立つことが示せた。
以上から、数学的帰納法と $n=1$ のときより、すべての正の整数 n に対して、 $f(n)\geqq g(n)$ が成り立つことが示せた。
（終）
解答編 つづき
問題
(2) $f(n)\geqq g(n)$ を示せ。
別解
(2)
$n$ が $2$ 以上の整数のとき\[ n=p_1^{a_1} \cdot p_2^{a_2} \cdots p_m^{a_m} \]と書ける。ここで、$a_1,\cdots,a_m$ は正の整数、 $p_1,\cdots,p_m$ は相異なる素数である。
この正の約数すべての和は\[ (1+p_1+\cdots+p_1^{a_1})\cdots (1+p_m+\cdots+p_m^{a_m}) \]と書ける。ここで、 $p_k$ を $3$ で割ったときの余りが $0,1,2$ のとき、それぞれ $r_k$ が $0,1,-1$ になるような $r_k$ を使うと\[ (1+r_1+\cdots+r_1^{a_1})\cdots (1+r_m+\cdots+r_m^{a_m}) \]は、すべて展開すると各項は、元の約数を $3$ で割った余りが $0,1,2$ のとき、対応する項が $0,1,-1$ となっている。なので、この和は、 $3$ で割ったときの余りが $1$ である正の約数の個数から $2$ である正の約数の個数を引いたものに一致するので、 $f(n)-g(n)$ と一致することがわかる。
ここで、 $(1+r_k+\cdots+r_k^{a_k})$ は、 $r_k=0$ なら $1$ であり、 $r_k=1$ なら $a_k+1$ であり、 $r_k=-1$ なら $0$ か $1$ なので、掛け合わせたものは $0$ 以上である。よって、 $f(n)\geqq g(n)$ である。
$n=1$ のときは $f(1)=1,g(1)=0$ なので、すべての正の整数について、 $f(n)\geqq g(n)$ が成り立つ。
（終）
解答編 つづき
問題
(3) $g(n)=15$ であるとき、 $f(n)$ のとりうる値を求めよ。
解答
(3)
正の整数 $n$ を以下のように表す。\[ n=3^{c} \cdot p_1^{a_1} \cdot p_2^{a_2} \cdots p_m^{a_m} \cdot q_1^{b_1} \cdot q_2^{b_2} \cdots q_k^{b_k} \]ここで、 $c$ は $0$ 以上の整数、 $a_1,\cdots,a_m,b_1,\cdots,b_k$ は正の整数、 $p_1,\cdots,p_m$ は相異なる素数で $3$ で割ったときの余りが $1$ 、 $q_1,\cdots,q_k$ は相異なる素数で $3$ で割ったときの余りが $2$ である。
(2)の計算を踏まえて考える。
正の整数 $N$ と $p^a$ との積（ $p$ は素数、 $a$ は正の整数）について、以下が成り立つ。
- $p \equiv 1 \pmod 3$ のときは、 $f(Np^a)=(a+1)f(N)$, $g(Np^a)=(a+1)g(N)$
- $p \equiv -1 \pmod 3$ かつ $a$ が奇数のときは、 $f(Np^a)=g(Np^a)$
- $p \equiv -1 \pmod 3$ かつ $a$ が偶数のときは、 $f(Np^a)-g(Np^a)=f(N)-g(N)$
2つ目より、$b_1,\cdots,b_k$ の中に奇数が含まれていれば、 $f(n)=g(n)$ となる。よって、例えば、 $N=2^{29}$ のときに、(2)(i) の計算より、 $f(n)=g(n)=15$ となることがわかる。
以下では、$b_1,\cdots,b_k$ がすべて偶数の場合を考える。\[ Q=q_1^{b_1} \cdot q_2^{b_2} \cdots q_k^{b_k} \]とすると、上のリストの３つ目より、\[ f(Q)-g(Q)=f(1)-g(1)=1 \]となることがわかる。
また、リストの１つ目より
\begin{eqnarray}
f(n) &=& (a_1+1)(a_2+1)\cdots(a_m+1)f(Q) \\[5pt]
g(n) &=& (a_1+1)(a_2+1)\cdots(a_m+1)g(Q) \\[5pt]
f(n)-g(n) &=& (a_1+1)(a_2+1)\cdots(a_m+1)
\end{eqnarray}$g(n)=15$ なので、 $C=(a_1+1)(a_2+1)\cdots(a_m+1)$ とおくと、 $C$ は $15$ の正の約数である。また、 $f(n)=g(n)+C$ なので、 $f(n)$ としてありうるものは、 $16,18,20,30$ である。
$n=2^{30}$ のとき、(2)(i)より、 $f(n)=\dfrac{30}{2}+1=16$, $g(n)=\dfrac{30}{2}=15$
$n=7^2\cdot 2^{10}$ のとき、(2)(i)と上の計算より、 $f(n)=(2+1)\cdot \left(\dfrac{10}{2}+1\right)=18$, $g(n)=3\cdot 5=15$
$n=7^4\cdot 2^{6}$ のとき、(2)(i)と上の計算より、 $f(n)=(4+1)\cdot \left(\dfrac{6}{2}+1\right)=20$, $g(n)=5\cdot 3=15$
$n=7^{14}\cdot 2^{2}$ のとき、(2)(i)と上の計算より、 $f(n)=(14+1)\cdot \left(\dfrac{2}{2}+1\right)=30$, $g(n)=15\cdot 1=15$
以上より、 $15,16,18,20,30$ …（答）
