https://spherical-harmonics.hateblo.jp/entry/Todai/2026/Rika

2026.03.02.19:08:49記

[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)$ がとりうる値を求めよ．

2026.03.02.19:08:49記
東大の整数の問題は最近は重たいように思います．自然数 $a，b$ の積 $ab$ を $3$ で割った余りが $2$ となるのは，片方が $3$ で割った余りが $2$ でもう片方を $3$ で割った余りが $1$ となる場合に限るので， $3$ で割った余りが $2$ となる数を複数乗じたとき，その結果を $3$ で割った余りが $2$ となるのは奇数回乗じたときに限ります．

[解答]
以下，整数 $l$ を $3$ で割った余りが $r$ （ $r=0，1，2$ ）であることを「 $l$ は $R(r)$ である」と略記する．

(1) $2800=2^4\cdot 5^2\cdot 7$ の正の約数の個数は $(4+1)(2+1)(1+1)=30$ 個であり， $R(0)$ なるものは存在しない．

$2800$ は $7$ 個の素数の積で，そのうち $R(2)$ であるものは $6$ 個である．ここで正の約数が $R(2)$ となるのは， $R(2)$ となる素数を奇数回乗じたものに限る．

(i) $R(1)$ となる素数を $1$ 回乗じたものは $2，5$ に $7$ を乗じるか否かの $4$ 個．

(ii) $R(1)$ となる素数を $3$ 回乗じたものは $2^3，2^2\cdot 5，2\cdot 5^2$ に $7$ を乗じるか否かの $6$ 個．

(iii) $R(1)$ となる素数を $5$ 回乗じたものは $2^4\cdot 5，2^3\cdot 5^2$ に $7$ を乗じるか否かの $4$ 個．

よって $g(n)=14$ ， $f(n)=30-14=16$ となる．

(2)(a) $n=3^a N$ （ $a$ は正の整数）としたとき $f(n)=f(N)$ ， $g(n)=g(N)$ であるから始めから $n$ は $3$ を素因数にもたないとして良い．

(b) $n$ を $R(2)$ となる素因数全ての積 $A$ と $R(1)$ となる素因数全ての積 $B$ の積によって $n=AB$ としたとき
$f(n)=f(A)f(B)$ ， $g(n)=g(A)f(B)$ であるから， $f(n)\geqq g(n)$ と $f(A)\geqq g(A)$ は同値であるから，始めから $n$ は $R(2)$ となる素因数しか持たないとして良い．

$p$ の指数が $k$ である正の約数が $R(1)$ のとき， $p$ の指数が $k-1$ である正の約数は $R(2)$ であり， $p$ の指数が $k$ である正の約数が $R(2)$ のとき， $p$ の指数が $k-1$ である正の約数は $R(1)$ であるから，

$p$ の指数が $k，k-1$ である $R(1)$ となる正の約数の個数と， $p$ の指数が $k，k-1$ である $R(2)$ となる正の約数の個数は等しい．…(★)

よって繰り返し(★)を用いることにより $k-2u-1\geqq 0$ （ $u$ は自然数）を満たす範囲内で「 $p$ の指数が $k，k-2u-1$ である $R(1)$ となる正の約数の個数と， $p$ の指数が $k，k-2u-1$ である $R(2)$ となる正の約数の個数は等しくなる．よって $k$ が奇数のときは $k=2u+1$ なる $u$ を考えることにより， $f(n)=g(n)$ となる．

つまり， $n$ の素因数分解を構成する $R(2)$ である素数の指数が奇数となるものが $1$ つでも存在すれば $f(n)=g(n)$ となる．そして $R(2)$ である素数の指数が全て偶数の場合は(★)を繰り返して素数の指数を全て $0$ にすることができ，このとき $n=1$ となるので $f(n)-g(n)=f(1)-g(1)=1$ となる．

よって $f(n)\geqq g(n)$ が言えた．

(3) (2)(b)を考えると $15=1\times 15=3\times 5=5\times 3=15\times 1$ であるから
$f(n)=15$ 以外に $(1+1)\times 15=15+15=30$ ， $(3+1)\times 5=15+5=20$ ， $(5+1)\times 3=15+3=18$ ， $(15+1)\times 1=15+1=16$ となりうる．

よって $f(n)=15$ ， $16$ ， $18$ ， $20$ ， $30$ となり得る．このとき $f(n)+g(n)=30$ ， $31$ ， $33=11\times 3$ ， $45=9\times 5$ ， $55=11\times 5$ に注意すると $2^{14}\times 7$ ， $2^{30}$ ， $2^{10}\times 7^{2}$ ， $2^{8}\times 7^{4}$ ， $2^{10}\times 7^{4}$ のときに $f(n)=15$ ， $16$ ， $18$ ， $20$ ， $30$ となることがわかる．

$f(n)=15$ 以外に例えば $(5+1)\times 3$ となりうる，としたときの $5+1$ の $+1$ は(2)(c)の $f(n)-g(n)=1$ に由来しています．つまり $n$ が $R(2)$ となる素因数のみで構成されるときの $f(n)=6，g(n)=5$ ですから， $R(2)$ である素数 $2$ を用いて $n=2^k$ としたとき， $2$ の冪乗は $2^0，2^1，2^2，…$ で $R(1)，R(2)$ が交互に登場するので， $R(1)$ が $6$ 回， $R(2)$ が $5$ 回登場する $k$ は $k=f(n)+g(n)-1=2f(n)=10$ （羃が $0$ から始まるので $1$ を引きます）となります．そして $(5+1)\times 3$ の $3$ は $R(1)$ となる素数の積で約数が $3$ 個のものを指していますので，例えば $7^2$ とすれば良いことがわかります．よって $f(n)=(5+1)\times 3=20$ となる例として $2^{10}\times 7^2$ を挙げることができるという訳です．

[大人の解答]として母関数を用いる解法もあります．

[大人の解答]
以下，整数 $l$ を $3$ で割った余りが $r$ （ $r=0，1，2$ ）であることを「 $l$ は $R(r)$ である」と略記する．

(2) $R(2)$ である素数 $p_1，…，p_k$ ， $R(1)$ である素数 $q_1，…，q_m$ を用いて
$n=p_1^{n_1}\cdots p_k^{n_k}\times q_1^{l_1}\cdots p_m^{l_m}$ のとき，
$F(x)=(1+x+\cdots+x^{n_1})\cdots(1+x+\cdots+x^{n_k})\times (l_1+1)\cdots (l_m+1)$
の偶数次の項の係数和が $f(n)$ で奇数次の項の係数和が $f(n)$ となるから
$F(1)=f(n)+g(n)$ ， $F(-1)=f(n)-g(n)$
が成立する．
$G(x)=1+x+\cdots+x^{u}$ について $G(-1)=\begin{cases} 0 & (u\mbox{が奇数}) \\ 1 & (u\mbox{が偶数}) \end{cases}$
であるから， $F(-1)\geqq 0$ となり $f(n)\geqq g(n)$ が成立する．

(2)の等号成立は $n_1，…，n_k$ の少なくとも $1$ つが奇数となることで，このとき
$f(x)=g(x)=\dfrac{1}{2}(n_1+1)\cdots (n_k+1)(l_1+1)\cdots (l_m+1)$ となります．
よって(3)で $g(x)=15$ のとき $30=(n_1+1)\cdots (n_k+1)(l_1+1)\cdots (l_m+1)$ で $n_1+1，…，n_k+1$ の少なくとも $1$ つが偶数となるので $30$ が $4$ で割れないことから $n_1，…，n_k$ のうち偶数は $1$ つしかありません．あとは $15$ を $3$ 以上の奇数の $1$ 個以上の積で表現する方法は $15，3\times 5$ だけなので $p_1\times P_2^{14}$ ， $p_1\times P_2^{3}\times P_3^5$ （ $p_1$ は $R(2)$ でなければならないが， $p_1$ ではない異なる素数 $P_2，P_3$ は $R(1)$ でも $R(2)$ でも良い）．

そして $n_1，…，n_k$ の全てが偶数のとき， $f(n)=g(n)+(l_1+1)\cdots (l_m+1)$ となります．また $f(n)+g(n)=(n_1+1)\cdots (n_k+1)(l_1+1)\cdots (l_m+1)$ ですから
$f(n)=\dfrac{1}{2}\{(n_1+1)\cdots (n_k+1)+1\}(l_1+1)\cdots (l_m+1)$ ，
$g(n)=\dfrac{1}{2}\{(n_1+1)\cdots (n_k+1)-1\}(l_1+1)\cdots (l_m+1)$
が成立します．よって(3)で $g(x)=15$ のとき $30=\{(n_1+1)\cdots (n_k+1)-1\}(l_1+1)\cdots (l_m+1)$ で $n_1+1，…，n_k+1$ の全てが奇数となるので $(n_1+1)\cdots (n_k+1)-1$ が偶数で $2，6，10，30$ の可能性があり，このとき $(n_1+1)\cdots (n_k+1)$ は $3，7，11，31$ と全て素数になっています（絶妙の設定）．よって $n_1=2，6，10，30$ のいずれかであり， $(l_1+1)\cdots (l_m+1)$ は奇数です．よって $(n_1，l_1)=(2，14)$ ， $(n_1，l_1，l_2)=(2，2，4)$ ， $(n_1，l_1)=(6，4)$ ， $(n_1，l_1)=(10，2)$ ， $(n_1)=(30)$ のいずれかとなります．つまり．
$p_1^{30}$ ， $p_1^{10}q_1^2$ ， $p_1^{6}q_1^4$ ， $p_1^{2}q_1^{14}$ ， $p_1^{2}q_1^{2}q_2^4$ の形のいずれかとなります．なお，
$f(p_1^{30})=16$ ， $f(p_1^{10}q_1^2)=18$ ， $f(p_1^{6}q_1^4)=20$ ， $f(p_1^{2}q_1^{14})=30$ ， $f(p_1^{2}q_1^{2}q_2^4)=30$ です．

この結果に基づいて具体例を提示すれば良いでしょう（ $3$ つの異なる素数の積の例を出す人はあまりいないように思いますが）．

2026.03.02.19:08:49記
[解答](2)を見直したら冗長（(2)(c)の議論だけで十分）でしたので同じ内容ですが書き直しておきます．

[解答]
以下，整数 $l$ を $3$ で割った余りが $r$ （ $r=0，1，2$ ）であることを「 $l$ は $R(r)$ である」と略記する．

(2) $n$ が $R(2)$ となる素数 $p$ を含むとする．このとき $p$ の指数が $k$ である正の約数が $R(1)$ のとき， $p$ の指数が $k-1$ である正の約数は $R(2)$ であり， $p$ の指数が $k$ である正の約数が $R(2)$ のとき， $p$ の指数が $k-1$ である正の約数は $R(1)$ であるから，

$p$ の指数が $k，k-1$ である $R(1)$ となる正の約数の個数と， $p$ の指数が $k，k-1$ である $R(2)$ となる正の約数の個数は等しい．…(★)

つまり， $n$ の素因数分解を構成する $R(2)$ である素数の指数が奇数となるものが $1$ つでも存在すれば $f(n)=g(n)$ となる．

ここで $R(2)$ である素数の指数が全て偶数の場合は(★)を繰り返して $R(2)$ である素数の指数を全て $0$ にしたとき（その素数を取り除いたとき）に $n$ が $n'$ になったとすると $f(n)-g(n)=f(n')-g(n')$ が成り立つ．ここで $n'$ は $R(1)$ である素数の積であるから $n'$ の約数は全て $R(1)$ となるので， $f(n')=(n'\mbox{の約数の個数})\gt 0$ ， $g(n')=0$ が成立する．
よって $f(n)-g(n)=f(n')-g(n')=(n'\mbox{の約数の個数})\gt 0$ となり $f(n)\gt g(n)$ となる．

よって $f(n)\geqq g(n)$ が言えた．