NF杯2024(P)

　特に断らない限り合同式は $5$ を法とする．$f(1)=1$ は $5$ の倍数ではない．$n\geq 2$ において，

$$\begin{aligned} f(n) & = \sum_{k=1}^n\frac{nk}{\text{gcd}(n,k)}\\ & = n\sum_{d|n} \sum_{\substack{1\leq k\leq n\\ \text{gcd}(n,k)=d}}\frac{k}{d}\\ &=n\sum_{d|n}\sum_{\substack{1\leq m\leq n/d\\ \text{gcd}(n/d,m)=1}}m\\ &=n\sum_{d|n}\sum_{\substack{1\leq m\leq d\\ \text{gcd}(d,m)=1}}m \end{aligned}$$

ここで，$d$ 以下の $d$ と互いに素な正の整数の個数を $\varphi(d)$ とすると，

$$\sum_{\substack{1\leq m\leq d\\ \text{gcd}(d,m)=1}}m =\begin{cases} 1&(d=1)\\ \dfrac{d}{2}\varphi(d)&(d\gt1) \end{cases}$$

が成り立つ．実際，$d=1$ のときは明らかで，$d\gt1$ のとき，$m$ が $d$ 以下の $d$ と互いに素な正の整数ならば $d-m$ もそうであるので，$d$ 以下の $d$ と互いに素な整数の値の平均は $\dfrac{d}{2}$ である．よってそのような整数の総和は $\dfrac{d}{2}\varphi(d)$ となる．

　恒等写像およびオイラー関数 $\varphi$ は乗法的であるので，関数 $n\varphi(n)$ も乗法的である．したがって素数 $p_1,\ldots,p_{\ell}$ と正の整数 $e_1,\ldots,e_{\ell}$ により $n=p_1^{e_1}\cdots p_\ell^{e_{\ell}}$ と素因数分解すれば，

$$\begin{aligned} f(n)&=n\Bigg(1+\sum_{d\gt1,d|n}\frac{d}{2}\varphi(d)\Bigg)\\ &=n\Bigg(\frac{1}{2}+\sum_{d|n}\frac{d}{2}\varphi(d)\Bigg)\\ &=\frac{n}{2}\Bigg(1+\sum_{d|n}d\varphi(d)\Bigg)\\ &=\frac{n}{2}\Bigg(1+\prod_{i=1}^{\ell}\left(\sum_{k=1}^{e_i}p_i^k\varphi(p_i^k)\right)\Bigg)\\ &=\frac{n}{2}\Bigg(1+\prod_{i=1}^{\ell}(1+p_i(p_i-1)+\cdots+p_i^{2e_i-1}(p_i-1))\Bigg)\\ &=\frac{n}{2}\Bigg(1+\prod_{i=1}^{\ell}(1-p_i+p_i^2-\cdots-p_i^{2e_i-1}+p_i^{2e_i})\Bigg)\\ &=\frac{n}{2}\Bigg(1+\prod_{i=1}^{\ell}\frac{p_i^{2e_i+1}+1}{p_i+1}\Bigg) \end{aligned}$$

よって，$f(n)$ が $5$ の倍数となるのは，$n$ が $5$ の倍数となるときか，

$$\prod_{i=1}^{\ell}\frac{p_i^{2e_i+1}+1}{p_i+1}\equiv -1\tag{i}$$

となるときのいずれかである．$N^{2024}$ の正の約数のうち $5$ の倍数であるものの個数は，$5$ の指数が $1$ 以上であるものの個数であるので，$100$ 以下の素数の個数が $25$ であることから，

$$2025^{24}\cdot 2024$$

と計算される．以下，$n$ は $5$ の倍数でないとする．

　$n$ の素因数 $p_i$ について， $\dfrac{p_i^{2e_i+1}+1}{p_i+1}$ が $5$ の倍数となるとすると，$p_i^{2e_i+1}\equiv-1$ より $p_i^{2(2e_i+1)}\equiv1$ となる．一方フェルマーの小定理より $p_i^4\equiv1$ であるので，$\gcd(2(2e_i+1),4)=2$ より $p_i^2\equiv1$ すなわち $p_i\equiv \pm1$ でなくてはならない．$p_i^{2e_i+1}\equiv-1$ と合わせると，$\dfrac{p_i^{2e_i+1}+1}{p_i+1}$ が $5$ の倍数となるのは $p_i\equiv-1$ のときに限られることが分かる．一方 $p_i\equiv-1$ のとき，

$$\dfrac{p_i^{2e_i+1}+1}{p_i+1}=1-p_i+p_i^2-\cdots+p_i^{2e_i}\equiv2e_i+1$$ となる．

　よって，$100$ 以下の素数のうち $5$ で割った余りが $1,2,3$ となるものを $q_1,\ldots,q_x$，余りが $4$ となるものを $r_1,\ldots,r_y$ とおき，それらに対応する指数をそれぞれ $f_1,\ldots,f_x,g_1,\ldots,g_y$ とすると，

$$\prod_{i=1}^x\frac{q_i^{2f_i+1}+1}{q_i+1}\not\equiv0, \quad\prod_{i=1}^y\frac{r_i^{2g_i+1}+1}{r_i+1}\equiv\prod_{i=1}^y(2g_i+1)$$

が成り立つ．特に，$5$ の倍数でない $N^{2024}$ の正の約数 $n$ のうち，

$$\prod_{1\leq i\leq \ell,p_i\neq r_y}\frac{p_i^{2e_i+1}+1}{p_i+1}=\Bigg(\prod_{i=1}^x\frac{q_i^{2f_i+1}+1}{q_i+1}\Bigg)\Bigg(\prod_{j=1}^{y-1}\frac{r_j^{2g_j+1}+1}{r_j+1}\Bigg)\not\equiv0$$

となるものの個数は，$j=1,\ldots,y-1$ に対して $2g_j+1\not\equiv0$ すなわち $g_j\not\equiv 2$ となるような $0$ 以上 $2024$ 以下の整数 $g_j$ の選び方を考えることで，

$$2025^x\cdot 1620^{y-1}$$

と計算できる．この条件が成り立っているとき，(i) が成り立つような $g_y$ の選び方は $5$ を法としてちょうど $1$ つ存在するので，$5$ の倍数でない $N^{2024}$ の正の約数 $n$ のうち (i) が成り立つものの個数は，

$$2025^x\cdot 1620^{y-1}\cdot405$$

　$100$ 以下の素数のうち $5$ で割って $4$ 余るのは，下一桁が $9$ である $19,29,59,79,89$ の $5$ 個であるので，$x=19,y=5$ となる．従って，$N^{2024}$ の正の約数のうち $f(n)$ が $5$ の倍数となるものの割合は，

$$\begin{aligned} \frac{a}{b}&=\frac{2025^{24}\cdot2024+2025^{19}\cdot 1620^4\cdot 405}{2025^{25}}\\ &=\frac{405^5\cdot(5^5\cdot2024+4^4)}{2025^6}\\ &=\frac{5^5\cdot2024+4^4}{2025\cdot 5^5}\\ &=\frac{6325256}{6328125} \end{aligned}$$

特に解答すべき値は $\bold{12653381}$ である．