代表選考合宿 2019
問題 1

$k\mid n$ のとき $d(sn)\gt d(sk)$ が常に成り立ち，同様に $n\mid k$ のときも $d(sn)=d(sk)$ は成り立たない．逆に $k\nmid n,n\nmid k$ のとき $d(sn)=d(sk)$ なる $s$ が存在することを示そう．

$nk$ がもつ素因数を $p_1,p_2,\dots,p_m$ とし，

$$n=\prod_{i=1}^{m}p_i^{a_i},\quad k=\prod_{i=1}^{m}p_i^{b_i}$$

とする．このとき，以下の等式を満たす整数 $s_1,s_2,\dots,s_m$ が存在することを示せばよい．

$$\dfrac{a_1+s_1}{b_1+s_1}\times \dfrac{a_2+s_2}{b_2+s_2}\times \cdots \times \dfrac{a_m+s_m}{b_m+s_m}=1$$

必要ならば任意の $i$ に対して $a_i\neq b_i$ とし，ある整数 $1\leq c\leq m-1$ が存在して $i=1,2,\dots,c$ に対して $a_i\gt b_i$，$i=c+1,c+2,\dots,m$ に対して $a_i\lt b_i$ とする．このとき満たしたい等式は

$$\prod_{i=1}^{c}\dfrac{a_i+s_i}{b_i+s_i}=\prod_{i=c+1}^{m}\dfrac{b_i+s_i}{a_i+s_i}$$

である．左辺について，$n_i(a_i-b_i)\gt b_i$ なる整数 $n_i$ をとり，$s_i=n_i(a_i-b_i)-b_i$ とする．さらにこの $n_i$ はある十分大きな整数より大きければ任意なので $n_i=cN+i-1$ とすれば

$$\prod_{i=1}^{c}\dfrac{a_i+s_i}{b_i+s_i}=\prod_{i=1}^{c}\dfrac{n_i+1}{n_i}=\prod_{i=1}^{c}\dfrac{cN+i}{cN+i-1}=\dfrac{N+1}{N}$$

が成り立つ．

同様に $s_{c+1},s_{c+2},\dots,s_m$ をうまく定めれば右辺も $\dfrac{N+1}{N}$ と等しくできるので，このように定めた $s$ に対して $d(sn)=d(sk)$ が成り立つ．