第6問 3で割った余りで分けた約数の個数

方針

解答

⓪ 発想(どう考え始めるか) 約数を3で割った余りは、その約数の素因数の余りを掛け合わせて決まる。$3$ で割って $1$ 余る素数はいくつ掛けても余りは $1$ のままだ。$2$ 余る素数は $2\equiv -1$ なので、掛けた個数の偶奇で余りが $1$ と $2$ に入れかわる。$3$ を因数にもつ約数は余りが $0$ で、どちらにも数えない。

この見方で、$f(n)-g(n)$ と $f(n)+g(n)$ を素因数の指数で表す。

① 余りの決まり方。 $n$ を

$$n=3^e\cdot m\cdot l$$

と分ける。$m$ は $3$ で割って $1$ 余る素数だけの積、$l$ は $2$ 余る素数だけの積で、$l=q_1^{b_1}{q}_2^{b_2}\cdots q_r^{b_r}$ とする。$3$ で割り切れない約数は $d=d_1{d}_2$($d_1$ は $m$ の約数、$d_2$ は $l$ の約数)と書ける。$d_2=q_1^{i_1}\cdots q_r^{i_r}$ のとき

$$d\equiv (-1{)}^{i_1+\cdots +i_r}(\mathrm{mod}3)$$

② (1) $2800$ のとき。 $2800=2^4\cdot 5^2\cdot 7$ で、$2\equiv 5\equiv -1$、$7\equiv 1$ である。約数 $2^a{5}^b{7}^c$ の余りは $a+b$ の偶奇で決まり、偶数なら $1$、奇数なら $2$ になる。

$a$ は $0$ から $4$ の $5$ 通り、$b$ は $0$ から $2$ の $3$ 通り。$a+b$ が偶数になる組は、ともに偶数の $3\cdot 2=6$ 組と、ともに奇数の $2\cdot 1=2$ 組で、合わせて $8$ 組。残りの $15-8=7$ 組は奇数になる。$c$ は $0,1$ の $2$ 通りなので

$$f(2800)=8\cdot 2=16,g(2800)=7\cdot 2=14$$

③ (2) 差を積の形で表す。 余り $1$ の約数に $+1$、余り $2$ の約数に $-1$ を割り当てて足すと、$f(n)-g(n)$ になる。① より、約数 $d_1{d}_2$ に割り当てる値は $(-1{)}^{i_1+\cdots +i_r}$ で、$d_1$ の選び方にはよらない。$m$ の約数の個数を $\tau (m)$ と書くと

$$f(n)-g(n)=\tau (m)\sum _{i_1=0}^{b_1}\cdots \sum _{i_r=0}^{b_r}(-1{)}^{i_1+\cdots +i_r}=\tau (m)\prod _{j=1}^r\left\{\sum _{i=0}^{b_j}(-1{)}^i\right\}$$

$\sum _{i=0}^b(-1{)}^i=1-1+1-\cdots$ は、$b$ が偶数なら $1$、奇数なら $0$ だ。よって

$$f(n)-g(n)=\{\begin{array}{ll}\tau (m)& (b_1,\dots ,b_r\text{がすべて偶数})\\ 0& (\text{奇数のものがある})\end{array}$$

どちらの場合も $0$ 以上なので、$f(n)\geqq g(n)$ である($l=1$ のときは積の部分がなく、$f(n)-g(n)=\tau (m)$)。

④ (3) 和も積の形で表す。 $3$ で割り切れない約数の個数は

$$f(n)+g(n)=\tau (m)(b_1+1)(b_2+1)\cdots (b_r+1)$$

$T=\tau (m)$、$U=(b_1+1)\cdots (b_r+1)$ とおく。

⑤ 奇数の $b_j$ があるとき。 $f(n)=g(n)$ なので $f(n)=15$。実際、$n=2^{29}$ では約数 $2^i$($0\leqq i\leqq 29$)の余りが $i$ の偶奇で決まり、$f=g=15$ となる。

⑥ $b_j$ がすべて偶数のとき。 $f-g=T$、$f+g=TU$ から

$$g(n)=\frac{T(U-1)}{2}=15,f(n)=g(n)+T=15+T$$

$U=1$ だと $g=0$ なので $U\geqq 3$。$U$ は奇数の積なので奇数で、$T(U-1)=30$ の $U-1$ は $30$ の偶数の約数 $2,6,10,30$ のどれかだ。それぞれ $T=15,5,3,1$ で、$f(n)=30,20,18,16$ になる。

どれも実際に起こる。$U=b+1$ となるよう $2^b$($b=2,6,10,30$)をとり、$T$ は $7^{T-1}$ でつくればよい。

よって $f(n)$ がとりうる値は $15,16,18,20,30$ である。

まとめ:$3$ で割って $2$ 余る素数は $-1$ のように働くので、約数の余りは指数の和の偶奇で決まる。$f-g$ も $f+g$ も素因数の指数の積で表せて、(2) は $f-g$ が $0$ か正のどちらかであること、(3) は2つの式の連立で調べた。

発展。 同じ考え方で、約数のうち $4$ で割って $1$ 余るものと $3$ 余るものの個数の差を考えると、それは $n$ を2つの平方数の和 $x^2+y^2$ で表す方法の数と結びつく(ヤコビの二平方定理)。$3$ で割った余りで分けた本問の差 $f(n)-g(n)$ は、$n=x^2+xy+y^2$ と表す方法の数と結びつくことが知られている。

別解

別解:(2) を、2余る素数を1つずつ外していく帰納法で示す。 $n$ が $3$ で割って $2$ 余る素数 $q$ を因数にもつとき、$n=q^b{n}^{\prime }$($n^{\prime }$ は $q$ で割り切れない)とする。$n$ の約数は $q^i{d}^{\prime }$($0\leqq i\leqq b$、$d^{\prime }$ は $n^{\prime }$ の約数)と書ける。$q^i$ を掛けると、$i$ が奇数なら余り $1$ と $2$ が入れかわり、偶数なら変わらない。したがって

$$f(n)-g(n)=\{f(n^{\prime })-g(n^{\prime })\}\sum _{i=0}^b(-1{)}^i$$

右の和は $b$ が偶数なら $1$、奇数なら $0$ だ。これをくり返して2余る素数をすべて外すと、残りは $3$ で割って $1$ 余る素数と $3$ だけの積になり、その約数の余りは $0$ か $1$ なので $f-g\geqq 0$ である。1段ごとに値は「そのまま」か「$0$」のどちらかになるので、最後まで $0$ 以上が保たれる。