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. 問題の構造
1.1 記法と基本分解
正の整数 $k$ の正の約数の個数を $\tau(k)$ と書き，空の積は $1$ とする。$n$ の素因数分解を
$$
n=3^{a}\prod_{i=1}^{r}p_i^{\alpha_i}\prod_{j=1}^{s}q_j^{\beta_j}=3^{a}PQ,\qquad p_i\equiv1,\quad q_j\equiv2\pmod 3
$$
と書く。ここで $a,r,s\geqq0$，$\alpha_i,\beta_j\geqq1$ であり，素数 $p_1,\dots,p_r,q_1,\dots,q_s$ は相異なる。さらに
$$
A=\tau(P)=\prod_{i=1}^{r}(\alpha_i+1),\qquad B=\tau(Q)=\prod_{j=1}^{s}(\beta_j+1),
$$
$$
S(n)=f(n)+g(n),\qquad D(n)=f(n)-g(n)
$$
とおく。$Q$ の正の約数 $q_1^{v_1}\cdots q_s^{v_s}$ を指数ベクトル $\boldsymbol v=(v_1,\dots,v_s)$ と同一視し，その全体と成分和を
$$
\mathcal V=\prod_{j=1}^{s}\lbrace 0,1,\dots,\beta_j\rbrace,\qquad \lvert\boldsymbol v\rvert=v_1+\cdots+v_s
$$
と書く（$\mathcal V$ の要素数は $B$）。最後に，整数 $d$ に対し $\chi(d)$ を $d\equiv1,\,2,\,0\pmod3$ に応じてそれぞれ $1,\,-1,\,0$ と定める。$\chi$ はすべての整数 $d,e$ について $\chi(de)=\chi(d)\chi(e)$ を満たし（完全乗法性），
$$
D(n)=\sum_{d\mid n}\chi(d)
$$
である。
(i) $n$ の正の約数のうち $3$ の倍数でないものは，$P$ の約数 $d_P$ と $Q$ の約数 $d_Q$ の積 $d_Pd_Q$ として一意に表される。
(ii) $d_Q$ の指数ベクトルを $\boldsymbol v$ とすると，$d_Pd_Q\equiv(-1)^{\lvert\boldsymbol v\rvert}\pmod3$ である。
(iii) $f(n)=A\,f(Q)$，$g(n)=A\,g(Q)$，$S(n)=AB$ である。ここで $f(Q)$，$g(Q)$ はそれぞれ $\lvert\boldsymbol v\rvert$ が偶数，奇数である $\boldsymbol v\in\mathcal V$ の個数に等しい。
(i) $3$ の倍数でない約数では $3$ の指数が $0$ であるから，素因数分解の一意性より従う。
(ii) $p_i\equiv1$，$q_j\equiv-1\pmod3$ より $d_Pd_Q\equiv\prod_{j}(-1)^{v_j}=(-1)^{\lvert\boldsymbol v\rvert}$。
(iii) (ii) より $d_Pd_Q$ の剰余は $d_P$ によらず $\lvert\boldsymbol v\rvert$ の偶奇だけで決まり，$d_P$ の選び方は $A$ 通りある。(i) と合わせて前半を得る。$S(n)$ は $3$ の倍数でない約数の総数であるから，(i) より $AB$ に等しい。
素因数の種類ごとの作用をまとめる。
| 素因数 | $\chi$ の値 | $f,g$ への作用 |
|---|---|---|
| $3$ | $0$ | 寄与しない（指数 $0$ の場合のみ数えられる） |
| $p\equiv1\pmod3$ | $1$ | $f,g$ をともに $\alpha+1$ 倍する |
| $q\equiv2\pmod3$ | $-1$ | 指数の偶奇によって剰余類を入れ替える |
本問は，$3$ を除去し，$P$ を共通の倍率 $A$ として分離したのち，直方体格子 $\mathcal V$ 上で成分和の偶奇を数える問題に帰着する。
1.2 指数格子の市松模様
$\mathcal V$ の点を $\lvert\boldsymbol v\rvert$ の偶奇で塗り分けると，隣接する点の色が交互に変わる多次元の市松模様が得られる。(1) の $2800=2^4\cdot5^2\cdot7$ では $Q=2^4\cdot5^2$，$\mathcal V=\lbrace0,\dots,4\rbrace\times\lbrace0,1,2\rbrace$ であり，$\lvert\boldsymbol v\rvert$ が偶数の点を $+$，奇数の点を $-$ で表すと次のようになる。
| $v_2\backslash v_1$ | $0$ | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|---|
| $0$ | $+$ | $-$ | $+$ | $-$ | $+$ |
| $1$ | $-$ | $+$ | $-$ | $+$ | $-$ |
| $2$ | $+$ | $-$ | $+$ | $-$ | $+$ |
$+$ は $8$ 個，$-$ は $7$ 個であり，$f(Q)=8$，$g(Q)=7$ である。この図から，(a) 両色の個数が一致するのはどのような場合か，(b) 一致しないとき差はいくつか，(c) 両色を結ぶ具体的な対応は何か，という問いが生じる。(a)(b) に代数的に答えるのが本解，(c) の対応を構成して答えるのが別解1 である。
1.3 和と差：二状態の分離
$3$ と互いに素な剰余類 $\lbrace1,2\rbrace$ の乗法は，符号 $\lbrace+1,-1\rbrace$ の乗法と同型である（$2\equiv-1$）。このため互いに素な $u,v$ の積では，二つの個数 $(f,g)$ が
$$
\begin{pmatrix}f(uv)\\ g(uv)\end{pmatrix}=\begin{pmatrix}f(v)&g(v)\\ g(v)&f(v)\end{pmatrix}\begin{pmatrix}f(u)\\ g(u)\end{pmatrix}
$$
のように混ざり合う（
補題5
）。この形の行列はすべて固有ベクトル $(1,1)^{\top}$，$(1,-1)^{\top}$ を共有し，対応する固有値はそれぞれ $f(v)+g(v)$，$f(v)-g(v)$ である。すなわち和 $S$ と差 $D$ は積に関して同時に対角化される座標であり，ともに乗法的になる。和は
補題2
により $S(n)=AB$ と直ちに決まるので，残る情報はすべて差 $D$ に集約される。
素数冪における $D$ の値は
$$
D(3^{a})=1,\qquad D(p^{\alpha})=\alpha+1,\qquad D(q^{\beta})=\sum_{k=0}^{\beta}(-1)^k=\frac{1+(-1)^{\beta}}{2}
$$
であり，いずれも非負である。これが (2) の不等式の局所的な理由であり，次の定理に集約される。
すべての正の整数 $n$ について
$$
D(n)=A\prod_{j=1}^{s}\frac{1+(-1)^{\beta_j}}{2}=\begin{cases}A&(Q\text{ が平方数})\\ 0&(Q\text{ が平方数でない})\end{cases}
$$
が成り立つ。ただし $Q=1$ は平方数とみなす。したがって
$$
f(n)=A\left\lceil\frac{B}{2}\right\rceil,\qquad g(n)=A\left\lfloor\frac{B}{2}\right\rfloor.
$$
1.4 構造定理の帰結
すべての正の整数 $n$ について次が成り立つ。
(a) $f(n)\geqq g(n)$。
(b) $A\mid f(n)$，$A\mid g(n)$，$f(n)-g(n)\in\lbrace0,A\rbrace$。
(c) $f(n)=g(n)$ であるための必要十分条件は，$Q$ が平方数でないことである。
(d) $f(n)>g(n)$ ならば $\gcd(f(n),g(n))=f(n)-g(n)=A$。特に $f(n)-g(n)\mid g(n)$。
(e) $g(n)>0$ ならば $g(n)\leqq f(n)\leqq2g(n)$ であり，右の等号は $B=3$ のときに限る。
(a)〜(c) は 定理3 から直ちに従う。(d) $B=2k+1$ と書くと $(f,g)=(A(k+1),Ak)$ であり，$\gcd(k+1,k)=1$ より $\gcd(f,g)=A$。(e) $f=g$ なら自明である。$f>g>0$ なら $B=2k+1$，$k\geqq1$ であり，$f/g=(k+1)/k\leqq2$，等号は $k=1$ のときに限る。
注意すべき点を挙げる。
- (c) の条件は $Q$ の平方性であり，$n$ の平方性ではない。$n=7$ では $Q=1$ で $(f,g)=(2,0)$，$n=10$ では $Q=10$ で $(f,g)=(2,2)$ である。
- $n=1$，$n=3^{a}$，一般に $Q=1$ の場合も定理に含まれ，$(f,g)=(A,0)$ となる。証明では空積と空の指数ベクトルを正しく扱う必要がある。
-
- に必要なのは (b) だけである。$g(n)=15$ なら $A\mid15$ かつ $f(n)-15\in\lbrace0,A\rbrace$。(e) の評価 $15\leqq f(n)\leqq30$ だけでは候補は絞り切れない。
1.5 作問の設計と解法の導出
以下は数値設定と設問構成からの分析であり，出題者の意図については推定を含む。
- 数値設定：$2800=2^4\cdot5^2\cdot7$ は $3$ で割り切れないので約数 $30$ 個すべてが計数対象となる。$q$ 型の素因数 $2,5$ の指数はともに偶数（$Q$ が平方数）で偏りが生じ，$p$ 型の素因数 $7$ が倍率 $A=2$ を与える。「倍率」と「偏り」がともに現れ，しかも $30$ 個の直接列挙が試験時間内に可能な規模である。具体計算から差が $\tau(P)$ になる現象に気づかせる誘導と読める。
- (2) の背景：$D(n)$ は二元二次形式 $x^2-xy+y^2$ による $n$ の表現数の $\frac16$ に等しい（ 3.5 節 ）。法 $4$ では，Jacobi の二平方定理 $r_2(n)=4\sum_{d\mid n}\chi_4(d)$（$\chi_4(d)$ は $d\equiv1,3\pmod4$ で $1,-1$，$d$ が偶数で $0$）から「$4$ で割って $1$ 余る約数は $3$ 余る約数より少なくない」が従うことが古典的に知られている。本問はその法 $3$ 版を，大学の理論を経由せず，素因数分解と偶奇だけで示させる設計と解釈できる。
- (3) の逆問題：$g(n)=15$ は奇数で，正の約数を $4$ 個もつ。答は $\tau(15)+1=5$ 個であり（ 定理12 ），$f=g$ の場合（$f=15$）の見落としと，必要条件のみで終える不備（実現例の欠落）を同時に判定できる。$15$ が奇数であることは，相補約数の対合による別解（ 3.4 節 ）も可能にする。
- 設問の連結：(2) の証明で得られる倍率 $A$ と差 $\lbrace0,A\rbrace$ が，そのまま (3) の鍵になる。
各構造から導かれる解法を整理する。着目する構造 数学的翻訳 導かれる解法 剰余類の乗法と符号の乗法の同型 和 $S$ と差 $D$ の乗法性 本解 具体的な数 $2800$ 偶奇の選び方の表 3.1 節 $f>g$ のときの $\gcd(f,g)=f-g$ 整除性による一括決定 3.2 節 指数格子の市松模様 偶奇を反転する対合 別解1 $g(n)=15$ が奇数 相補約数の対合の固定点 別解2 $D(n)=\sum_{d\mid n}\chi(d)$ の非負性 二次形式の表現数 参考解1 同上（$n\equiv1\pmod3$ の場合） 3-core 分割の個数 参考解2
2. 本解：和と差の乗法性
2.1 方針
$f,g$ を個別に数えず，和 $S=f+g$ と差 $D=f-g$ を扱う。互いに素な積について $S,D$ がともに乗法的であることを示し（ 1.3 節 ），素数冪での値から 定理3 を得る。(1) は $S,D$ の連立で，(2) は $D\geqq0$ で，(3) は $A\mid g$ と $D\in\lbrace0,A\rbrace$ による必要条件と，実現例の構成による十分性で処理する。
2.2 解答
準備
互いに素な正の整数 $u,v$ について
$$
f(uv)=f(u)f(v)+g(u)g(v),\qquad g(uv)=f(u)g(v)+g(u)f(v)
$$
が成り立つ。したがって $S(uv)=S(u)S(v)$，$D(uv)=D(u)D(v)$ である。
$\gcd(u,v)=1$ より，$uv$ の正の約数は $u$ の約数 $d$ と $v$ の約数 $e$ の積 $de$ として一意に表される。$3\nmid de$ となるのは $3\nmid d$ かつ $3\nmid e$ のときに限り，このとき
$$
1\cdot1\equiv2\cdot2\equiv1,\qquad 1\cdot2\equiv2\cdot1\equiv2\pmod3
$$
であるから，二式を得る。辺々加減すると
$$
S(uv)=\bigl(f(u)+g(u)\bigr)\bigl(f(v)+g(v)\bigr),\qquad D(uv)=\bigl(f(u)-g(u)\bigr)\bigl(f(v)-g(v)\bigr).
$$
素数冪での値を求める。$3^{a}$ の正の約数のうち $3$ の倍数でないものは $1$ のみであるから $S(3^{a})=D(3^{a})=1$。$p\equiv1\pmod3$ なら $p^k\equiv1$ であるから $S(p^{\alpha})=D(p^{\alpha})=\alpha+1$。$q\equiv2\pmod3$ なら $q^k\equiv(-1)^k$ であるから
$$
S(q^{\beta})=\beta+1,\qquad D(q^{\beta})=\sum_{k=0}^{\beta}(-1)^k=\frac{1+(-1)^{\beta}}{2}.
$$
$S(1)=D(1)=1$ であり，素因数分解に現れる相異なる素数の冪は互いに素であるから，
補題5
と素因数の種類の個数に関する帰納法により
$$
S(n)=AB,\qquad D(n)=A\prod_{j=1}^{s}\frac{1+(-1)^{\beta_j}}{2}.
$$
これで
定理3
が示された。
(1)
$2800=2^4\cdot5^2\cdot7$ であり，$2\equiv5\equiv2$，$7\equiv1\pmod3$ であるから，$P=7$，$Q=2^4\cdot5^2$，$A=2$，$B=5\cdot3=15$ である。$Q$ は平方数であるから
$$
f(2800)+g(2800)=AB=30,\qquad f(2800)-g(2800)=A=2.
$$
よって
$$
f(2800)=16,\qquad g(2800)=14.
$$
(2)
素数冪における $D$ の値はすべて非負整数であり，$D(n)$ はそれらの積であるから $D(n)\geqq0$，すなわち $f(n)\geqq g(n)$ である。等号が成り立つのは $Q$ が平方数でないとき，かつそのときに限る。
(3)
$g(n)=15$ とする。
必要条件。
補題2
より $15=g(n)=A\,g(Q)$ であり，$g(Q)$ は非負整数であるから $A\mid15$，すなわち $A\in\lbrace1,3,5,15\rbrace$。また
定理3
より $f(n)-15\in\lbrace0,A\rbrace$。よって
$$
f(n)\in\lbrace15,\,16,\,18,\,20,\,30\rbrace.
$$
十分性。$n=2^{29}$ とすると $A=1$，$B=30$ であり，$B$ が偶数なので $f(n)=g(n)=15$。次に $c\in\lbrace1,3,5,15\rbrace$ に対し
$$
n=2^{30/c}\cdot7^{\,c-1}
$$
とおくと $A=c$，$B=\frac{30}{c}+1$ であり，$c$ は奇数だから $\frac{30}{c}$ は偶数，$B$ は奇数である。よって
定理3
より
$$
g(n)=c\cdot\frac{B-1}{2}=15,\qquad f(n)=c\cdot\frac{B+1}{2}=15+c.
$$
$c=1,3,5,15$ により $f(n)=16,18,20,30$ が実現する。
以上より，$f(n)$ のとりうる値は
$$
f(n)=15,\ 16,\ 18,\ 20,\ 30.
$$
実現例を表にまとめる。
| $f(n)$ | $n$ の例 | $A$ | $B$ |
|---|---|---|---|
| $15$ | $2^{29}$ | $1$ | $30$ |
| $16$ | $2^{30}$ | $1$ | $31$ |
| $18$ | $2^{10}\cdot7^{2}$ | $3$ | $11$ |
| $20$ | $2^{6}\cdot7^{4}$ | $5$ | $7$ |
| $30$ | $2^{2}\cdot7^{14}$ | $15$ | $3$ |
解答のまとめ
| 設問 | 答 |
|---|---|
| (1) | $f(2800)=16,\ g(2800)=14$ |
| (2) | すべての正の整数 $n$ で $f(n)\geqq g(n)$（等号は $Q$ が平方数でないときに限る） |
| (3) | $f(n)=15,\ 16,\ 18,\ 20,\ 30$ |
2.3 検証・検算
-
- の直接列挙：$2800$ の正の約数のうち $3$ で割って $1$ 余るものは $1,4,7,10,16,25,28,40,70,100,112,175,280,400,700,2800$ の $16$ 個，$2$ 余るものは $2,5,8,14,20,35,50,56,80,140,200,350,560,1400$ の $14$ 個であり，本解と一致する。
- 小さい $n$：$n=1,2,4,7,10,12$ に対する $(f,g)$ はそれぞれ $(1,0),(1,1),(2,1),(2,0),(2,2),(2,1)$ であり，$D(1)=1$，$D(2)=0$，$D(4)=1$，$D(7)=2$，$D(10)=0$，$D(12)=D(3)D(4)=1$ は局所値の積に一致する。
- 和と差の偶奇：$S-D=2g$ であるから $S\equiv D\pmod2$ でなければならない。(1) では $S=30$，$D=2$ がともに偶数である。
-
- の整合性：正の差 $f-15\in\lbrace1,3,5,15\rbrace$ はすべて $15$ の約数であり， 補題4 (d) に適合する。上限 $f\leqq2g=30$（(e)）も満たし，上限は $B=3$ で達成される。
-
- の解の形：$f>15$ のとき $B\in\lbrace31,11,7,3\rbrace$ はすべて素数であるから，$Q$ はただ一つの素数の冪 $q^{B-1}$ である。$A$ も奇数なので $P$ は平方数であり，$n/3^{a}$ は平方数になる。特に $f=16$ を与える $n$ は $3^{a}q^{30}$ の形に限り，その最小値は $2^{30}$ である。
3. 別解と参考解
3.1，3.2 節は特定の設問に対する他の導出，3.3，3.4 節は高校数学の範囲で完結する別解，3.5，3.6 節は大学数学の既知定理を用いる参考解である。3.7 節で同じ系列に属する変形を，3.8 節で解法の比較をまとめる。
3.1 (1) の他の導出：偶奇の選び方の表
着想・方針
補題2 より $f(2800)=2f(Q)$，$g(2800)=2g(Q)$（$Q=2^4\cdot5^2$）である。$\lvert\boldsymbol v\rvert=v_1+v_2$ の偶奇は $v_1,v_2$ の偶奇の組で決まるから，座標ごとの偶数値・奇数値の個数を掛け合わせればよい。
解答
| 素数冪 | 指数の範囲 | 偶数の指数 | 奇数の指数 |
|---|---|---|---|
| $2^4$ | $0\leqq v_1\leqq4$ | $3$ 個 | $2$ 個 |
| $5^2$ | $0\leqq v_2\leqq2$ | $2$ 個 | $1$ 個 |
$\lvert\boldsymbol v\rvert$ が偶数となるのは（偶，偶）と（奇，奇）の組であるから
$$
f(Q)=3\cdot2+2\cdot1=8,\qquad g(Q)=3\cdot1+2\cdot2=7.
$$
よって $f(2800)=16$，$g(2800)=14$。
検証・検算
1.2 節 の表の $+$ と $-$ の個数に一致する。この計算は，座標ごとの偶数値・奇数値の個数 $(e_j,o_j)$ を行列 $\begin{pmatrix}e_j&o_j\\ o_j&e_j\end{pmatrix}$ で合成する方法（ 3.7 節 ）の $s=2$ の場合であり，差 $(3-2)(2-1)=1$ をとれば本解の $D(Q)=1$ に戻る。
3.2 (3) の他の導出：最大公約数による一括決定
着想・方針
補題4 (d) により，$f>g$ のとき差 $f-g$ は $\gcd(f,g)$ に等しい。この不変量を用いると，倍率 $A$ に言及せずに $f-15$ が $15$ の正の約数であることが分かる。
解答
$g(n)=15$ とする。$f(n)=g(n)$ なら $f(n)=15$。$f(n)>g(n)$ なら 補題4 (d) より $f(n)-15=\gcd(f(n),15)$ は $15$ の正の約数であるから，$f(n)\in\lbrace16,18,20,30\rbrace$。十分性は 2.2 節 の実現例による。
検証・検算
実現例の組 $(f,g)=(16,15),(18,15),(20,15),(30,15)$ の最大公約数はそれぞれ $1,3,5,15$ で，差に一致する。本解が用いた $A\mid g$ は 補題2 だけから従うのに対し，$\gcd(f,g)=f-g$ は $f,g$ の完全な公式（ 定理3 の後半）を要する。必要とする情報は多いが，「差が最大公約数に等しい」という形は，実現可能な組の特徴付け（ 定理12 ）の条件そのものである。
3.3 別解1：指数格子の対合
着想・方針
1.2 節 の市松模様において，色の異なる点を具体的に組にする。各座標の値を $(0,1),(2,3),\dots$ と隣接する二数の組に分け，組をもつ座標のうち番号最小のものだけを動かす。この規則により操作は対合となり，対応せずに残る点を完全に特定できる。
解答
補題2
より $f(n)=A\,f(Q)$，$g(n)=A\,g(Q)$ であり，$f(Q),g(Q)$ は $\lvert\boldsymbol v\rvert$ が偶数，奇数である $\boldsymbol v\in\mathcal V$ の個数である。
各 $j$ について，集合 $E_j\subset\lbrace0,1,\dots,\beta_j\rbrace$ と写像 $\pi_j:E_j\to E_j$ を
$$
E_j=\lbrace v : 0\leqq v\leqq\beta_j,\ v\text{ は奇数，または }v\text{ は偶数かつ }v < \beta_j\rbrace,\qquad \pi_j(v)=\begin{cases}v+1&(v\text{ が偶数})\\ v-1&(v\text{ が奇数})\end{cases}
$$
で定める。$E_j$ から除かれる値は，$\beta_j$ が偶数のときの $\beta_j$ のみである。
$$
\mathcal V^{\ast}=\lbrace\boldsymbol v\in\mathcal V : \text{ある }j\text{ で }v_j\in E_j\rbrace
$$
とし，$\boldsymbol v\in\mathcal V^{\ast}$ に対して $j(\boldsymbol v)=\min\lbrace j : v_j\in E_j\rbrace$ とおき，$\iota(\boldsymbol v)$ を $\boldsymbol v$ の第 $j(\boldsymbol v)$ 成分を $\pi_{j(\boldsymbol v)}(v_{j(\boldsymbol v)})$ に置き換えたものと定める。
$\iota$ は $\mathcal V^{\ast}$ から $\mathcal V^{\ast}$ への写像で $\iota\circ\iota=\mathrm{id}$ を満たし，$\lvert\iota(\boldsymbol v)\rvert$ と $\lvert\boldsymbol v\rvert$ の偶奇は異なる。また
$$
\mathcal V\setminus\mathcal V^{\ast}=\begin{cases}\varnothing&(\text{ある }\beta_j\text{ が奇数})\\ \lbrace(\beta_1,\dots,\beta_s)\rbrace&(\text{すべての }\beta_j\text{ が偶数})\end{cases}
$$
である（$s=0$ のときは後者で，$\mathcal V$ は空の指数ベクトル $1$ 点からなる）。
$\pi_j$ は $E_j$ を $E_j$ に移し（$v$ が偶数で $v < \beta_j$ なら $v+1\leqq\beta_j$ は奇数，$v$ が奇数なら $v-1$ は偶数で $v-1 < \beta_j$），$\pi_j\circ\pi_j=\mathrm{id}$ を満たし，値の偶奇を反転する。
$\boldsymbol w=\iota(\boldsymbol v)$，$j=j(\boldsymbol v)$ とする。$\boldsymbol w$ は第 $j$ 成分だけが $\boldsymbol v$ と異なり，$w_j=\pi_j(v_j)\in E_j$，かつ $k < j$ では $w_k=v_k\notin E_k$ である。よって $\boldsymbol w\in\mathcal V^{\ast}$，$j(\boldsymbol w)=j$ であり，$\iota(\boldsymbol w)$ は第 $j$ 成分を $\pi_j(\pi_j(v_j))=v_j$ に戻したもの，すなわち $\boldsymbol v$ である。成分和の偶奇は第 $j$ 成分の偶奇とともに反転する。
最後に，$\boldsymbol v\notin\mathcal V^{\ast}$ はすべての $j$ で $v_j\notin E_j$ を意味し，$\lbrace0,\dots,\beta_j\rbrace\setminus E_j$ は $\beta_j$ が奇数なら空集合，偶数なら $\lbrace\beta_j\rbrace$ である。
補題6 より，$\iota$ は $\mathcal V^{\ast}$ の中で成分和が偶数の点と奇数の点との間の全単射を与える。
- ある $\beta_j$ が奇数のとき：$\mathcal V^{\ast}=\mathcal V$ であるから $f(Q)=g(Q)$。
- すべての $\beta_j$ が偶数のとき（$Q=1$ を含む）：対応しない点は $(\beta_1,\dots,\beta_s)$ のみであり，その成分和は偶数であるから $f(Q)=g(Q)+1$。
したがって
$$ f(Q)-g(Q)=\prod_{j=1}^{s}\frac{1+(-1)^{\beta_j}}{2},\qquad f(n)-g(n)=A\bigl(f(Q)-g(Q)\bigr) $$
となり， 定理3 の前半が示された。
- は $f(n)-g(n)\geqq0$ から従う。(1) では $Q=2^4\cdot5^2$ の対応しない点は $(4,2)$，すなわち約数 $400\equiv1\pmod3$ であり，$f(Q)=g(Q)+1$ と $f(Q)+g(Q)=15$ から $(f(Q),g(Q))=(8,7)$，これを $A=2$ 倍して $f(2800)=16$，$g(2800)=14$。(3) は 2.2 節 と同じ議論により $f(n)=15,16,18,20,30$。
検証・検算
- $Q=2^4\cdot5^2$ では，たとえば $(0,0)\leftrightarrow(1,0)$（約数 $1\leftrightarrow2$），$(4,0)\leftrightarrow(4,1)$（約数 $16\leftrightarrow80$）が組になり，$(4,2)$（約数 $400$）だけが残る。
- 残る点は角 $(\beta_1,\dots,\beta_s)$ であって中央 $(\beta_1/2,\dots,\beta_s/2)$ ではない。反射 $v_j\mapsto\beta_j-v_j$ は $\beta_j$ が奇数なら偶奇を反転するが，偶数なら保存するので，すべての $\beta_j$ が偶数の場合の相殺には使えない。実際，$\beta_j=2$ の中央値 $1$ は奇数である。
- 点の総数 $B$ が奇数であることだけでは，残る $1$ 点の色は決まらない。色を決めているのは対合の具体的な構成である。
3.4 別解2：相補約数の対合と平方数の検出
着想・方針
- の条件 $g(n)=15$ が奇数であることに着目する。約数 $d$ と相補約数 $m/d$ の対応は二度で元に戻る対合であり，奇数個の集合上の対合は固定点をもつ。固定点は $d^2=m$ を意味するので，素因数分解の詳細に入る前に平方性が導かれる。
解答
$n=3^{a}m$，$3\nmid m$ とおく。$3$ の倍数である約数は数えないので $f(n)=f(m)$，$g(n)=g(m)$ である。$m$ の正の約数 $d$ に対し $\kappa(d)=m/d$ とおくと，$\kappa\circ\kappa=\mathrm{id}$ かつ $\chi(d)\chi(\kappa(d))=\chi(m)$ である。
$3\nmid m$ とする。
(i) $m\equiv2\pmod3$ ならば $f(m)=g(m)$ である。
(ii) $m\equiv1\pmod3$ ならば，$g(m)$ が奇数であることは，$m=t^2$，$t\equiv2\pmod3$ を満たす正の整数 $t$ が存在することと同値である。同様に，$f(m)$ が奇数であることは，$m=t^2$，$t\equiv1\pmod3$ を満たす正の整数 $t$ が存在することと同値である。
(i) $\chi(m)=-1$ より，$\kappa$ は剰余類 $1$ の約数全体と剰余類 $2$ の約数全体の間の全単射である。
(ii) $\chi(m)=1$ より，$\kappa$ は $G=\lbrace d\mid m : d\equiv2\pmod3\rbrace$ を $G$ に移す対合である。$G$ は $\kappa$ の固定点と，$2$ 元集合 $\lbrace d,\kappa(d)\rbrace$（$d\neq\kappa(d)$）とに分割されるから，$G$ の要素数の偶奇は固定点の個数の偶奇に等しい。固定点は $d^2=m$ を満たす $d\in G$ であり，存在すれば $d=\sqrt m$ に限る。よって $g(m)$ が奇数であることは，$\sqrt m$ が整数でかつ $\sqrt m\equiv2\pmod3$ であることと同値である。$f$ についても同様である。
- を解く。$g(n)=g(m)=15$ とする。
- $m\equiv2\pmod3$ のとき： 補題7 (i) より $f(n)=g(n)=15$。
- $m\equiv1\pmod3$ のとき：$15$ は奇数であるから，
補題7
(ii) より $m=t^2$（$t\equiv2\pmod3$）。よって $m=PQ$ の各素因数の指数はすべて偶数であり，$Q$ は平方数，$A,B$ はともに奇数である。$Q$ が平方数のときの偶奇計数 $f(Q)-g(Q)=1$（
2.2 節
または
3.3 節
）と
補題2
より $f(n)-g(n)=A$，$g(n)=A\cdot\frac{B-1}{2}=15$。したがって $A\mid15$ であり，$f(n)=15+A\in\lbrace16,18,20,30\rbrace$。
以上より $f(n)\in\lbrace15,16,18,20,30\rbrace$ であり，十分性は 2.2 節 の実現例による。
検証・検算
- 実現例との対応：$n=2^{29}$ では $m=2^{29}\equiv(-1)^{29}\equiv2\pmod3$ で第一の場合，$n=2^{10}\cdot7^2$ では $m=(2^5\cdot7)^2$，$t=224\equiv2\pmod3$ で第二の場合にあたる。
- 補題7 (i) の逆は成り立たない。$m=10\equiv1\pmod3$ でも $f(10)=g(10)=2$ である。ただし $g(m)$ が奇数という条件の下では，(ii) により「$f(m)=g(m)\iff m\equiv2\pmod3$」が成り立つ。
- 平方数と分かるのは $3$ の冪を除いた $m$ であり，$n$ ではない。$n=3\cdot2^{30}$ でも $(f,g)=(16,15)$ である。
- この別解の独自の寄与は「$g$ が奇数なら，$m\equiv2\pmod3$ であるか $m$ が平方数であるかのいずれか」という二分法であり，候補値の決定には $Q$ が平方数のときの偶奇計数を別途要する。
3.5 参考解1：Eisenstein 整数のノルム計数
着想・方針
符号付きの和 $D(n)$ を，ある集合の要素の個数として表せば，非負性は自明になる。$\omega=\frac{-1+\sqrt{-3}}{2}$ とし，Eisenstein 整数環 $\mathbb Z[\omega]=\lbrace x+y\omega : x,y\in\mathbb Z\rbrace$ と，そのノルム
$$
N(x+y\omega)=(x+y\omega)\overline{(x+y\omega)}=x^2-xy+y^2
$$
を用いる。
解答
次の事実は代数的整数論の標準的な結果である。
(i) $\mathbb Z[\omega]$ は Euclid 整域であり，$0$ でも単数でもない元は，単数倍と順序を除いて一意に素元の積に分解される。単数は $\pm1,\pm\omega,\pm\omega^2$ の $6$ 個である。ノルムは乗法的である。
(ii) 有理素数 $\ell$ は次のように分解する。$\ell=3$ は $3=-\omega^2(1-\omega)^2$（$N(1-\omega)=3$）。$\ell\equiv1\pmod3$ は，互いに同伴でない共役な素元 $\pi,\bar\pi$ により $\ell=\pi\bar\pi$（$N(\pi)=\ell$）。$\ell\equiv2\pmod3$ は $\mathbb Z[\omega]$ でも素元であり，$N(\ell)=\ell^2$。
$R(n)=\left\lvert\lbrace(x,y)\in\mathbb Z^2 : x^2-xy+y^2=n\rbrace\right\rvert$ とおくと，すべての正の整数 $n$ について $R(n)=6D(n)$ が成り立つ。
$R(n)$ はノルム $n$ の元 $z\in\mathbb Z[\omega]$ の個数である。$n>0$ より $z\neq0$ であり，$z$ の単数倍 $6$ 個は相異なり，ノルムも等しい。よって $R(n)=6I(n)$，ただし $I(n)$ はノルム $n$ の元の同伴類の個数である。
$z$ の素因子のノルムは $n$ を割り切るから，$z$ の素元分解には $n$ の素因数を割り切る素元しか現れない。
定理8
より，ノルム $n=3^{a}\prod_ip_i^{\alpha_i}\prod_jq_j^{\beta_j}$ の元の同伴類は
$$
z\sim(1-\omega)^{c}\prod_{i}\pi_i^{x_i}\bar\pi_i^{\,y_i}\prod_{j}q_j^{\,w_j}\qquad(p_i=\pi_i\bar\pi_i)
$$
の形に一意に表され，$N(z)=n$ は $c=a$，$x_i+y_i=\alpha_i$，$2w_j=\beta_j$ と同値である。よって
$$
I(n)=\prod_{i=1}^{r}(\alpha_i+1)\prod_{j=1}^{s}\frac{1+(-1)^{\beta_j}}{2}
$$
であり，これは
2.2 節
で求めた $D(n)$ の積表示に一致する。
- の証明。$R(n)$ は個数であるから $R(n)\geqq0$。よって
補題9
より $D(n)=R(n)/6\geqq0$。
上の証明は，局所因子の一致を確かめる段階で 2.2 節 と同じ計算を用いる。したがって (2) の証明としての独立性は，表現数公式 $R(n)=6\sum_{d\mid n}\chi(d)$ を既知の定理として引用するか否かに依存する。この参考解の価値は，符号付きの差 $D(n)$ を「原点中心，半径 $\sqrt n$ の円周上にある六角格子点の個数の $\frac16$」として，すなわち非負の幾何的対象の個数として解釈する点にある（ 5.6 節 ）。
検証・検算
- $n=1$：$R(1)=6$（単数），$D(1)=1$。
- $n=7$：$7=(3+\omega)(3+\bar\omega)$，$N(3+\omega)=9-3+1=7$ であり，$R(7)=12$，$D(7)=2$。
- $n=2$：$4(x^2-xy+y^2)=(2x-y)^2+3y^2=8$ は整数解をもたないので $R(2)=0$，$D(2)=0$。
- $n=2800$：$R(2800)=12$（たとえば $20(3+\omega)=60+20\omega$ と $20(3+\bar\omega)=40-20\omega$ の単数倍），$D(2800)=2$ と一致する。
- 六角格子の $6$ 回回転対称性だけから得られるのは $6\mid R(n)$ までであり，$R(n)=6D(n)$ には素元分解による計数が必要である。
3.6 参考解2：3-core 分割
着想・方針
$D(3k+1)$ は，整数 $k$ の 3-core 分割の個数に等しい。$3$ の冪を除いた部分が $3$ で割って $1$ 余るか $2$ 余るかで場合分けすれば，(2) は分割の個数の非負性に帰着する。
解答
非負整数 $k$ の分割 $\lambda=(\lambda_1\geqq\lambda_2\geqq\cdots)$ の Young 図形の各マス $c$ について，$c$ の右にあるマスの個数と下にあるマスの個数の和に $1$ を加えたものを $c$ のフック長という。すべてのマスのフック長が $3$ の倍数でない分割を 3-core 分割といい，その個数を $a_3(k)$ と書く（空分割により $a_3(0)=1$）。
すべての非負整数 $k$ について $a_3(k)=D(3k+1)$ が成り立つ。母関数で書けば
$$
\sum_{k\geqq0}a_3(k)z^k=\prod_{\ell\geqq1}\frac{(1-z^{3\ell})^3}{1-z^{\ell}}=\sum_{k\geqq0}D(3k+1)z^k.
$$
第一の等号は $t$-core 分割の母関数 $\prod_{\ell}(1-z^{t\ell})^t/(1-z^{\ell})$ の $t=3$ の場合であり，第二の等号は非自明な $q$ 級数恒等式である。$a_3(k)=D(3k+1)$ は Granville–Ono がモジュラー形式の理論を用いて示し，Hirschhorn–Sellers（2009）が Jacobi の三重積公式に基づく初等的証明を与えた。
5.7 節
では，これを
補題9
に帰着させる証明の概略を述べる。
(2) の証明。$n=3^{a}m$，$3\nmid m$ とおくと $D(n)=D(m)$ である。
- $m\equiv1\pmod3$ のとき：$m=3k+1$ と書けて， 定理10 より $D(n)=a_3(k)\geqq0$。
- $m\equiv2\pmod3$ のとき：
補題7
(i) より $D(n)=0$。
よってすべての $n$ で $D(n)\geqq0$ である。
検証・検算
- $k=0,1,2,3,4$ の 3-core 分割はそれぞれ「空分割」，「$(1)$」，「$(2),(1,1)$」，「なし」，「$(3,1),(2,1,1)$」であり，$a_3(k)=1,1,2,0,2$ は $D(1),D(4),D(7),D(10),D(13)=1,1,2,0,2$ に一致する。$k=3$ の分割 $(3),(2,1),(1,1,1)$ はいずれも左上のマスのフック長が $3$ である。
- $2800=3\cdot933+1$ であるから $a_3(933)=D(2800)=2$ となる。
- 恒等式は $3k+1$ の形の数にしか適用できないので，$3$ の冪の除去と $m\equiv2\pmod3$ の場合の処理が不可欠である。
3.7 同じ系列に属する変形
以下は独立の解法とは数えず，既出の解法の表現違い，または構成の変種として扱う。
本解（乗法性）の系列
符号付き約数和の積公式
$\chi$ の完全乗法性から
$$
D(n)=\sum_{d\mid n}\chi(d)=\prod_{\ell^{e}\parallel n}\bigl(1+\chi(\ell)+\chi(\ell)^2+\cdots+\chi(\ell)^{e}\bigr)
$$
であり，各因子は $1$（$\ell=3$），$e+1$（$\ell\equiv1$），$0$ または $1$（$\ell\equiv2$）である。本解を一行に圧縮した形である。
生成関数の $X=\pm1$ での評価
$H(X)=A\prod_{j}(1+X+\cdots+X^{\beta_j})$ とおくと，偶数次・奇数次の係数和がそれぞれ $f(n),g(n)$ であるから
$$
f(n)=\frac{H(1)+H(-1)}{2},\qquad g(n)=\frac{H(1)-H(-1)}{2},\qquad H(1)=AB,\quad H(-1)=D(n).
$$
二状態漸化式と遷移行列
$q\nmid m$ のとき，$q^{\beta}$ の指数のうち偶数の個数を $e=\lfloor\beta/2\rfloor+1$，奇数の個数を $o=\lceil\beta/2\rceil$ とすると
$$
\begin{pmatrix}f(mq^{\beta})\\ g(mq^{\beta})\end{pmatrix}=\begin{pmatrix}e&o\\ o&e\end{pmatrix}\begin{pmatrix}f(m)\\ g(m)\end{pmatrix}.
$$
固有値 $e+o=\beta+1$，$e-o\in\lbrace0,1\rbrace$ に対応する固有ベクトルが $(1,1)^{\top}$，$(1,-1)^{\top}$ であり，$D(mq^{\beta})=(e-o)D(m)$ と $D(1)=1$ から帰納法で $D\geqq0$ を得る。
打ち消しによる縮約
$q\equiv2\pmod3$，$q\nmid m$ のとき，$m$ の各約数 $d$ について $d,qd,\dots,q^{\beta}d$ の剰余類は交互に並ぶ。隣同士を打ち消すと，$D(q^{\beta}m)$ は $\beta$ が偶数なら $D(m)$，奇数なら $0$ である。同様に $D(p^{\alpha}m)=(\alpha+1)D(m)$（$p\nmid m$），$D(3^{a}m)=D(m)$（$3\nmid m$）。特に，$q\mid n$ であっても $D(q^2n)=D(n)$ が成り立つ。$q$ 型素因数の指数は偶奇だけが意味をもち，$n$ は $D$ を保ったまま $P\prod_{\beta_j\text{ が奇数}}q_j$ に縮約される。
確率・期待値
$3$ と互いに素な約数を一様に選ぶと，$q_j$ の指数 $V_j$ は独立で $\lbrace0,\dots,\beta_j\rbrace$ 上一様であり
$$
\frac{D(n)}{S(n)}=\mathbb E\bigl[(-1)^{V_1+\cdots+V_s}\bigr]=\prod_{j=1}^{s}\frac{1}{\beta_j+1}\sum_{v=0}^{\beta_j}(-1)^v=\begin{cases}1/B&(B\text{ が奇数})\\ 0&(B\text{ が偶数})\end{cases}
$$
となる。独立性が乗法性に対応する。偏りの比がとりうる値は $0,1,\frac13,\frac15,\dots$ に限られ，いずれも実現する。
重み付き和による強化
$\sigma>0$ に対し $W_\sigma(n)=\sum_{d\mid n}\chi(d)\,d^{-\sigma}$ も同様に積に分解する。$q$ 型の因子は $z=q^{-\sigma}\in(0,1)$ として
$$
\sum_{k=0}^{\beta}(-z)^k=\frac{1-(-z)^{\beta+1}}{1+z}>0
$$
であり，他の因子も正である。よって $W_\sigma(n)>0$ であり，有限和なので $\sigma\to+0$ として $D(n)\geqq0$ を得る。厳密な不等式を経由するが，根拠は同じ局所因子の乗法性である。
Liouville 関数による表示
$D(n)=A\sum_{d\mid Q}(-1)^{\Omega(d)}$ と書ける（ 5.5 節 ）。等号条件が平方数判定そのものであることを示す表示である。
別解1（対合）の系列
市松模様とドミノ敷き詰め
別解1 の対合 $\iota$ で組になる $2$ 点は一つの座標で $1$ だけ異なるので，$\iota$ は $\mathcal V^{\ast}$ の隣接 $2$ 点による敷き詰め（ドミノタイリング）を与え，各ドミノは両色を $1$ 点ずつ覆う。すべての辺の長さ $\beta_j+1$ が奇数なら点の総数は奇数で，$\mathcal V$ 全体の敷き詰めは不可能であるが，その事実だけでは余る点の色は決まらない。色の決定には具体的な敷き詰めが必要である。
一筆書き（一般化 Gray code）
場合分けを経ずに $f(Q),g(Q)$ を同時に決める構成である。
$\mathcal V$ の $B$ 個の点を，$\boldsymbol v^{(0)}=\boldsymbol 0$ から始まり，隣り合う $2$ 点が一つの成分でちょうど $1$ だけ異なるように一列 $\boldsymbol v^{(0)},\dots,\boldsymbol v^{(B-1)}$ に並べることができる。このとき $\lvert\boldsymbol v^{(k)}\rvert\equiv k\pmod2$ であり
$$
f(Q)=\left\lceil\frac{B}{2}\right\rceil,\qquad g(Q)=\left\lfloor\frac{B}{2}\right\rfloor.
$$
$s$ に関する帰納法による。$s=0$ では $\mathcal V$ は $1$ 点で自明である。$s-1$ 次元の格子 $\mathcal V'=\prod_{j < s}\lbrace0,\dots,\beta_j\rbrace$ に条件を満たす列 $\gamma$ があるとする。$\mathcal V$ を層 $\mathcal V'\times\lbrace c\rbrace$（$c=0,1,\dots,\beta_s$）の順にたどり，$c$ が偶数の層では $\gamma$ を順方向に，奇数の層では逆方向にたどる。層の内部では $\gamma$ の性質により条件が満たされる。層の継ぎ目では，前の層の終点と次の層の始点が $\gamma$ の同じ端点に対応するので，第 $s$ 成分だけが $1$ 増える。始点は $\boldsymbol 0$ である。隣り合う点で成分和の偶奇が反転するので $\lvert\boldsymbol v^{(k)}\rvert\equiv k\pmod2$ であり，$0\leqq k\leqq B-1$ のうち偶数は $\lceil B/2\rceil$ 個である。
局所的な対の構成（別解1）に対し，これは格子全体を一本の交互列に並べる大域的な構成である。
奇数基の混合基数表示
すべての $\beta_j$ が偶数のとき $b_j=\beta_j+1$ はすべて奇数であり，
$$
t=v_1+b_1v_2+b_1b_2v_3+\cdots+(b_1\cdots b_{s-1})v_s
$$
は $\mathcal V$ から $\lbrace0,1,\dots,B-1\rbrace$ への全単射で，係数がすべて奇数なので $t\equiv\lvert\boldsymbol v\rvert\pmod2$ である。よって $f(Q)=\frac{B+1}{2}$。ある $\beta_j$ が奇数の場合は，その座標での隣接ペアにより $f(Q)=g(Q)$ とする。
採用しなかった方法
- 約数そのものを $1$ の $3$ 乗根の指数に代入する $\sum_{d\mid n}\omega^{d}$：$\omega^{de}=\omega^{d}\omega^{e}$ は一般に成り立たず，素数冪ごとの積に分解できない。乗法性を保つのは $\chi(d)$ である。
- 相補約数の対応 $d\leftrightarrow m/d$ のみによる (2) の証明：$m\equiv1\pmod3$ では剰余類が保存され，大小が決まらない。
- 反射 $v_j\mapsto\beta_j-v_j$ によって「中央の指数が残る」とする議論：すべての $\beta_j$ が偶数のとき反射は偶奇を保存し，中央点の成分和は奇数にもなりうる。誤りである。
- 微分・積分・凸性などの連続的手法：対象は有限集合の偶奇と積構造で完全に決まり，連続化は簡約をもたらさない。
- 六角格子の回転対称性のみ，あるいは Euler 標数・Witten 指数との類比のみによる議論：$6\mid R(n)$ や形式的な対応を与えるにとどまり，非負性の証明にならない（ 5.8 節 ）。
3.8 解法の比較
| 解法 | 主に利用する構造 | 対象 | 範囲 | 長所 | 注意点 |
|---|---|---|---|---|---|
| 本解 | 和・差の乗法性 | 全設問 | 高校 | 局所計算だけで全設問を統一，記述量が最小 | $\gcd(u,v)=1$ の明示，$3^{a}$ の寄与は $1$ |
| 3.1 節 | 偶奇の選び方の表 | (1) | 高校 | 定義に最も近く検算に向く | 素因数が多いと煩雑 |
| 3.2 節 | $\gcd(f,g)=f-g$ | (3) | 高校 | 候補を一括決定 | $f,g$ の完全な公式が必要 |
| 別解1 | 指数格子の対合 | 全設問 | 高校 | 対応を構成し，残る点まで特定 | 対合性の検証，残るのは角の点 |
| 別解2 | 相補約数の対合 | (3) | 高校 | 奇数性から平方数を検出 | 偶奇計数を別途要する |
| 参考解1 | Eisenstein 整数のノルム | (2) | 大学 | 差を個数として解釈 | 素元分解の理論が必要 |
| 参考解2 | 3-core 分割 | (2) | 大学 | 約数と分割の接続 | 恒等式の証明が高度 |
試験場での第一選択は本解である。(1)〜(3) が同じ補題から導かれ，(3) で必要な情報（$A\mid g$，$D\in\lbrace0,A\rbrace$）が (2) の証明の副産物として得られる。別解1 は計算量が同程度で，不等式の理由を具体的な対応として示す点で説明力が高い。別解2 は (3) の数値の奇数性を活かす着眼として価値がある。参考解は試験の答案には過剰であるが，差 $D(n)$ が非負になる理由を，二次形式・分割という異なる対象の個数として説明する。
4. 汎用的な探索手順
本問から抽出される，「約数（より一般に乗法的に生成される対象）を合同条件で分類して数える」問題に対する探索手順を述べる。
4.1 意思決定の流れ
- 分類条件の乗法構造を調べる。法 $m$ と互いに素な剰余類は群 $(\mathbb Z/m\mathbb Z)^{\times}$ をなし，本問では位数 $2$ の群 $\lbrace\pm1\rbrace$ と同型である。素数をその剰余類で分類する。
- 結果に影響しない自由度を除く。法を割る素数（本問の $3$）は寄与せず，剰余類が単位元である素数（本問の $p$）は共通の倍率を与えるだけである。
- 個数が二つなら和と差を考える。一般には群の指標で分解する（ 5.4 節 ）。和は総数として自明なことが多い。
- 局所（素数冪）での値を求め，乗法性で合成する。あるいは局所的な対合を作り，番号最小の座標だけを動かす規則で大域的な対合に組み上げる。
- 大小比較では対合の固定点を特定する。固定点の個数と所属が差を与える。
- 値が指定された逆問題では，整除性や不変量（$\gcd$ など）で必要条件を作り，自由度の少ない族（本問の $2^{x}7^{y}$）で実現例を構成して十分性を示す。
- 指定された個数が奇数なら，自然な対合の固定点を探す。約数の相補対応の固定点は平方根である。
- 検算する。境界（$n=1$，$3^{a}$，$Q=1$），小さい $n$ の列挙，$S\equiv D\pmod2$，必要条件と十分性の両方による照合を行う。
4.2 症状と有効な表現
| 症状 | 検討する表現・道具 | 本問での例 |
|---|---|---|
| 約数を剰余類で分類する | 素因数ごとの剰余と指数への分解 | 1.1 節 |
| 二つの個数が積で混ざる | 和と差，指標による対角化 | 本解，1.3 節 |
| 剰余類が $\pm1$ のように掛け合わさる | 指数和の偶奇，交代和 | 2.2 節 |
| 個数の大小比較 | 偶奇を反転する対合と固定点 | 別解1 |
| 指定された個数が奇数 | 相補対応 $d\leftrightarrow m/d$ の固定点 | 別解2 |
| 指定値からの逆算 | 整除性，$\gcd$ などの不変量，標準形の族 | 本解 (3)，3.2 節 |
| 符号付き和の非負性 | 別の対象の個数としての解釈 | 参考解1，参考解2 |
| 交代和が素数冪ごとに分かれる | 生成関数の $X=-1$ 代入，遷移行列 | 3.7 節 |
4.3 類題への適用
同じ構造は，値が $0,\pm1$ の完全乗法的関数（実数値の Dirichlet 指標）が与えられれば常に現れる。たとえば次が成り立ち，いずれも本解・別解1 がそのまま通用する。
- 法 $4$：奇数の約数のうち $4$ で割って $1$ 余るものの個数は $3$ 余るものの個数以上であり，差は「$3$ で割って $2$ 余る素数」を「$4$ で割って $3$ 余る素数」に読み替えた 定理3 の式で与えられる。
- 奇素数 $\ell$ を法とする平方剰余：$\ell$ と互いに素な約数のうち $\ell$ を法とする平方剰余であるものの個数は，平方非剰余であるものの個数以上である（
定理13
）。
いずれの場合も，指標の値が $-1$ である素数の指数の偶奇が差を決める。作問の観点からは，(i) 具体例で倍率と偏りの両方が現れる数を選ぶ，(ii) 不等式を一般に示させる，(iii) 一方の個数を固定した逆問題で整除性と実現を問う，という三段構成が，この構造を過不足なく検査する設計原理になっている。
5. 発展事項
5.1 高校数学と一般理論の境界
| 事項 | 高校数学での扱い | 一般理論 |
|---|---|---|
| 剰余類の乗法 | $2\equiv-1$，符号の規則 | $(\mathbb Z/3\mathbb Z)^{\times}\cong C_2$，Dirichlet 指標 |
| 和と差 | 連立して $f,g$ を復元 | 群環 $\mathbb Z[C_2]$ の指標による分解 |
| 差の積公式 | 展開と因数分解 | 乗法的関数，Dirichlet 畳み込み $\mathbf 1\ast\chi$ |
| 差の非負性 | 局所因子が $0,1,\alpha+1$ | 実指標の約数和の非負性，$\zeta_K=\zeta\cdot L(\cdot,\chi)$ |
| 平方数の判定 | 指数がすべて偶数 | Liouville 関数の約数和 |
| 偶奇の対応 | 隣接する指数の組 | 符号反転対合，Gray code |
| 差の個数解釈 | 扱わない | 二元二次形式の表現数，Eisenstein 整数のイデアル |
| 分割との関係 | 扱わない | 3-core 分割，abacus 表示 |
本解，別解1，別解2，3.1，3.2 節および 3.7 節の大半は左欄の範囲で完結する。右欄は，それらの計算が成り立つ理由を説明する理論である。
5.2 実現可能な組と $g(n)=k$ の完全分類
非負整数の組 $(F,G)$ について，$(F,G)=(f(n),g(n))$ を満たす正の整数 $n$ が存在するための必要十分条件は
$$
F=G\geqq1\qquad\text{または}\qquad F>G\geqq0\ \text{かつ}\ (F-G)\mid G
$$
である（$0$ はすべての正の整数で割り切れるとする）。特に正の整数 $k$ について
$$
\lbrace f(n) : g(n)=k\rbrace=\lbrace k\rbrace\cup\lbrace k+c : c\text{ は }k\text{ の正の約数}\rbrace
$$
であり，その要素数は $\tau(k)+1$ である。
必要性。$B$ が偶数なら $F=G=AB/2\geqq1$。$B$ が奇数なら $F-G=A\geqq1$，$G=A\cdot\frac{B-1}{2}$ より $(F-G)\mid G$。
十分性。任意の $A,B\geqq1$ について $N=7^{A-1}2^{B-1}$ は $\tau(P)=A$，$\tau(Q)=B$ を満たすから，
定理3
より $(f(N),g(N))=\left(A\lceil B/2\rceil,\,A\lfloor B/2\rfloor\right)$。$F=G=k\geqq1$ なら $(A,B)=(1,2k)$ とし，$F>G$ で $c=F-G$ が $G$ を割り切るなら $(A,B)=(c,\,2G/c+1)$ とすればよい。
後半は $G=k\geqq1$ の場合であり，$k$ と $k+c$（$c\mid k$）はすべて相異なるので要素数は $1+\tau(k)$ である。
$(f(n),g(n))$ は二つの不変量 $A=\tau(P)$，$B=\tau(Q)$ だけで決まり，任意の $(A,B)$ が $2$ と $7$ の冪の積 $7^{A-1}2^{B-1}$ で実現される。本問 (3) は $k=15$，$\tau(15)+1=5$ の場合である。
5.3 Dirichlet 指標と乗法的関数
$\chi$ は法 $3$ の唯一の非自明な Dirichlet 指標であり，Kronecker 記号 $\left(\frac{-3}{d}\right)$ に一致する。$D=\mathbf 1\ast\chi$（Dirichlet 畳み込み）であるから，乗法的関数の畳み込みとして $D$ は乗法的である。
補題5
はこの特別な場合にあたる。Dirichlet 級数では，$\operatorname{Re}s>1$ において
$$
\sum_{n=1}^{\infty}\frac{D(n)}{n^{s}}=\zeta(s)L(s,\chi)=\zeta_{K}(s),\qquad K=\mathbb Q(\sqrt{-3})
$$
が成り立つ。$\zeta_K$ は $K$ の Dedekind ゼータ関数であり，$n^{-s}$ の係数はノルム $n$ のイデアルの個数である。これが参考解1 の背景である。Euler 積の各因子は素数の分解型（分岐・完全分解・惰性）に対応する：
$$
\zeta_K(s)=\frac{1}{1-3^{-s}}\prod_{\ell\equiv1\ (3)}\frac{1}{(1-\ell^{-s})^{2}}\prod_{\ell\equiv2\ (3)}\frac{1}{1-\ell^{-2s}}.
$$
(2) の不等式は，次の一般定理の特殊な場合である。
$h:\mathbb Z_{>0}\to\mathbb R$ を $h(1)=1$ を満たす完全乗法的関数とする。このとき
$$
\sum_{d\mid n}h(d)\geqq0\quad(\text{すべての }n\geqq1)\iff h(\ell)\geqq-1\quad(\text{すべての素数 }\ell)
$$
が成り立つ。
($\Rightarrow$) $n=\ell$ とおけば $1+h(\ell)\geqq0$。
($\Leftarrow$) $\sum_{d\mid n}h(d)=\prod_{\ell^{e}\parallel n}\bigl(1+h(\ell)+\cdots+h(\ell)^{e}\bigr)$ であり，$x\geqq-1$ のとき $1+x+\cdots+x^{e}\geqq0$ である。実際，$x\geqq0$ なら自明，$x=-1$ なら値は $0$ または $1$，$-1 < x < 0$ なら値は $\frac{1-x^{e+1}}{1-x}>0$ である。
実数値の Dirichlet 指標 $\psi$ は $\psi(\ell)\in\lbrace0,\pm1\rbrace$ を満たすから，常に $\sum_{d\mid n}\psi(d)\geqq0$ である。$\psi=\chi_4$ のとき，これは Jacobi の公式 $r_2(n)=4\sum_{d\mid n}\chi_4(d)$ が示す二平方和の表現数の非負性と同じ内容であり，$\psi$ が奇素数 $\ell$ を法とする Legendre 記号のときは 4.3 節 の平方剰余の主張になる。
5.4 二状態の分離：群環と指標
約数の剰余類の分布を群環の元として記録する。$C_2=\lbrace1,\varepsilon\rbrace$（$\varepsilon$ が剰余類 $2$ に対応）として
$$
F_n=f(n)\cdot1+g(n)\cdot\varepsilon\in\mathbb Z[C_2]\cong\mathbb Z[X]/(X^2-1)
$$
とおくと，
補題5
は互いに素な $u,v$ について $F_{uv}=F_uF_v$ を意味する。$C_2$ の二つの指標 $X\mapsto1$，$X\mapsto-1$ は環準同型 $\mathbb Z[X]/(X^2-1)\to\mathbb Z$ を与え，$F_n$ をそれぞれ $S(n)$，$D(n)$ に写す。生成関数の $X=\pm1$ への代入（3.7 節），遷移行列の対角化（1.3 節），期待値 $\mathbb E[(-1)^{V_1+\cdots+V_s}]$，Dirichlet 指標は，いずれもこの指標による分解（$C_2$ 上の離散 Fourier 変換）の別表現である。なお $F\mapsto(S,D)$ は単射であるが全射ではなく，像は $S\equiv D\pmod2$ を満たす組からなる。2.3 節の検算はこの事実による。
一般の法 $m$ では $F_n\in\mathbb Z[(\mathbb Z/m\mathbb Z)^{\times}]$ となり，剰余類 $c$ に属する約数の個数は指標の直交関係により
$$
\frac{1}{\varphi(m)}\sum_{\psi}\overline{\psi(c)}\sum_{d\mid n}\psi(d)
$$
で与えられる（$\psi$ は法 $m$ の Dirichlet 指標全体を動く）。群の位数が $2$ を超えると複素数値の指標が現れ，個々の剰余類の個数は複数の指標の寄与の和として表される。
5.5 Liouville 関数と平方数判定
$\Omega(d)$ を重複を込めた $d$ の素因数の個数とし，$\lambda(d)=(-1)^{\Omega(d)}$ を Liouville 関数という。$Q$ の素因数はすべて $\chi$ の値が $-1$ であるから，$d\mid Q$ について $\chi(d)=\lambda(d)$ であり
$$
D(n)=A\sum_{d\mid Q}\lambda(d),\qquad \sum_{d\mid m}\lambda(d)=\begin{cases}1&(m\text{ が平方数})\\ 0&(m\text{ が平方数でない})\end{cases}
$$
が成り立つ。後者は任意の正の整数 $m$ について成り立つ恒等式で，素数冪ごとの交代和 $\sum_{k=0}^{e}(-1)^k$ の積として示される。Dirichlet 級数では $\sum_{n}\lambda(n)n^{-s}=\zeta(2s)/\zeta(s)$ と同値である。本問の等号条件（
補題4
(c)）は，この平方数判定の特殊な場合である。
5.6 六角格子・二次形式・回転不変部分格子
$\Lambda=\mathbb Z+\mathbb Z\omega\subset\mathbb C$ は六角格子（正三角形格子）であり，$N(z)=\lvert z\rvert^2$ である。したがって
補題9
は
$$
6D(n)=\bigl(\text{原点中心，半径 }\sqrt n\text{ の円周上にある }\Lambda\text{ の点の個数}\bigr)
$$
と読める。$u=2x-y$，$v=y$ とおくと $4(x^2-xy+y^2)=u^2+3v^2$ である。$u,v$ の偶奇が異なれば $u^2+3v^2$ は奇数であるから，$u^2+3v^2=4n$ の解では $u\equiv v\pmod2$ となり，$(x,y)=\left(\frac{u+v}{2},v\right)$ と戻せる。よって $6D(n)$ は $u^2+3v^2=4n$ の整数解の個数でもある。
格子そのものを数えることもできる。有限指数の部分格子 $L\subset\Lambda$ で $\omega L=L$ を満たすもの（$L=-L$ と合わせて $60^\circ$ 回転で不変なもの）は，$\mathbb Z[\omega]$ の $0$ でないイデアルにほかならない。$\mathbb Z[\omega]$ は単項イデアル整域であるから $L=z\Lambda$ と書け，$[\Lambda:z\Lambda]=N(z)$ である。したがって
$$
D(n)=\left\lvert\lbrace L\subset\Lambda : [\Lambda:L]=n,\ \omega L=L\rbrace\right\rvert
$$
であり，$D(n)$ は回転対称性を保つ指数 $n$ の部分格子の個数である。たとえば $D(7)=2$ は $(3+\omega)\Lambda$ と $(3+\bar\omega)\Lambda$ に対応し，$D(2)=0$ は指数 $2$ の部分格子（$3$ 個ある）がいずれも回転で不変でないことに対応する。
5.7 3-core 分割と abacus 表示
$t$-core 分割は，abacus（そろばん）表示によって成分の和が $0$ の整数ベクトル $(n_0,\dots,n_{t-1})$ と一対一に対応し，分割の大きさは $\frac t2\sum_i n_i^2+\sum_i i\,n_i$ で与えられる（Garvan–Kim–Stanton，1990）。$t=3$ で $(n_1,n_2)=(-v,-u)$ とおくと，3-core 分割は $(u,v)\in\mathbb Z^2$ と一対一に対応し，その大きさは
$$
k=3(u^2+uv+v^2)-2u-v
$$
となる。$x=3u-1$，$y=3v$ とおけば $x^2+xy+y^2=3k+1$ であり，
$$
a_3(k)=\left\lvert\lbrace(x,y)\in\mathbb Z^2 : x^2+xy+y^2=3k+1,\ x\equiv2,\ y\equiv0\pmod3\rbrace\right\rvert.
$$
ここで $x^2+xy+y^2=N(x-y\omega)$ である。$\mathbb Z[\omega]/3\mathbb Z[\omega]$ の単数群は位数 $6$ で，$\pm1,\pm\omega,\pm\omega^2$ の像がそれを尽くす。したがってノルムが $3$ と互いに素な元 $z$ の $6$ 個の単数倍のうち，$z\equiv2\pmod{3\mathbb Z[\omega]}$ を満たすものはちょうど一つである。$z=x-y\omega\equiv2$ は $x\equiv2$，$y\equiv0\pmod3$ と同値であるから，右辺は $R(3k+1)/6$ に等しく，
補題9
により $a_3(k)=D(3k+1)$ を得る。すなわち
定理10
は abacus による全単射を認めれば
補題9
に帰着し，参考解1 と参考解2 は六角格子という共通の背景をもつ。$4(3k+1)=(2x+y)^2+3y^2$ と書き直せば，Baruah–Nath（2014）による定式化「$x^2+3y^2$ による $12k+4$ の表現数は $6a_3(k)$」にも一致する。
5.8 位相的・物理的な類似
実射影空間 $\mathbb RP^{\beta}$ は各次元に一つずつ胞体をもつ胞体分割をもつので，その Euler 標数は $e(\mathbb RP^{\beta})=\sum_{k=0}^{\beta}(-1)^k$ であり，Euler 標数は直積について乗法的である。したがって
$$
D(n)=A\cdot e\bigl(\mathbb RP^{\beta_1}\times\cdots\times\mathbb RP^{\beta_s}\bigr).
$$
また，成分和の偶奇で符号を付けた和は，超対称量子力学の Witten 指数 $\operatorname{Tr}(-1)^{F}$ と形式的に同じ形をしており，別解1 の対合は「対をなして打ち消し合う状態」と「残る状態」の区別に相当する。ただしこれらは形式的な対応にとどまる。Euler 標数は一般には負にもなりうるので，非負性の根拠にはならない。非負性を保証しているのは，本問に固有の局所因子の値（$0$ または $1$）と，対合の固定点の具体的な特定である。
5.9 歴史的背景
約数の剰余類と二次形式の関係の原型は，Fermat の二平方定理（17 世紀）と，その表現数を与える Jacobi の公式 $r_2(n)=4\sum_{d\mid n}\chi_4(d)$（1829）である。二元二次形式の体系的理論は Gauss の『整数論』（1801）に始まり，Dirichlet は算術級数定理（1837）の証明のために指標と $L$ 関数を導入して，二次形式の表現数と類数の理論を展開した。$\mathbb Z[\omega]$ の算術は三次相互法則の研究の中で発展し，Eisenstein が 1844 年にその証明を公表した。$t$-core 分割は対称群のモジュラー表現論（ブロックの分類に関する Nakayama 予想）に起源をもち，その組合せ論的・数論的研究は Garvan–Kim–Stanton（1990），Granville–Ono（1996）らによって進められた。$a_3(k)=D(3k+1)$ の初等的証明は Hirschhorn–Sellers（2009）による。本問は，これらの理論が交わる最も初等的な場面の一つになっている。
6. 最終整理
6.1 全体の構造マップ
- 約数の剰余類の計数
- 各設問
- (1)：$S=30$，$D=2$ → $(f,g)=(16,14)$（別法：偶奇の表）
- (2)：$D(n)\geqq0$，等号は $Q$ が平方数でないとき
- (3)：必要条件 $A\mid15$，$f-15\in\lbrace0,A\rbrace$（別法：$\gcd$，相補約数の対合）→ 十分性 $2^{29}$，$2^{30/c}7^{c-1}$ → $f=15,16,18,20,30$
- 一般化
6.2 解答一覧
| 設問 | 答 |
|---|---|
| (1) | $f(2800)=16,\ g(2800)=14$ |
| (2) | $f(n)-g(n)\in\lbrace0,\tau(P)\rbrace$ より $f(n)\geqq g(n)$ |
| (3) | $f(n)=15,\ 16,\ 18,\ 20,\ 30$ |
6.3 数学的教訓
- 剰余類の乗法構造を先に読む。$2\equiv-1\pmod3$ により，約数の剰余類の計数は指数和の偶奇の計数になる。
- 結果に効かない自由度（$3$ の冪）と，一律の倍率を与えるだけの自由度（$p$ 型の素因数）を先に分離する。
- 二つの個数が積で混ざるなら和と差をとる。和は総数として自明であり，差は乗法的で，局所因子 $0,1,\alpha+1$ の積になる。
- 個数の比較は対合で行える。番号最小の座標だけを動かす規則が対合性を保証し，残るのは角の点である。中央の点ではない。
- 逆問題は「必要条件（整除性・不変量）」と「実現例の構成」の両方で閉じる。$f=g$ の場合を落とさない。
- 符号付きの和の非負性は，しばしば別の対象（二次形式の表現，イデアル，分割）の個数として説明される。ただしその同一視自体が非自明な定理であり，証明の独立性はどこまでを既知とするかに依存する。
- 境界（$n=1$，$Q=1$，空積）と，平方性が問われる対象（$n$ ではなく $Q$ や $m$）を正確に扱う。
