OMC182(F)

　 $d$ を $n$ の正の約数とする．$\gcd(k,n)=d$ となる必要十分条件は， $k$ が $d$ の倍数かつ $\gcd \left( \dfrac kd, \dfrac nd \right) = 1$ となることである．したがって，$\gcd(k,n)$ を固定して数え上げると， $$\begin{aligned} f(n) &= \sum_{d \mid n}d\times\phi\bigg(\frac{n}{d}\bigg) \\ &= \sum_{d\mid n}\frac{n}{d}\times\phi(d) \\ &= n\sum_{d\mid n}\dfrac{\phi(d)}{d} \end{aligned}$$ を得る．ここで， $g(d)=\dfrac{\phi(d)}{d}$ は乗法的関数（任意の互いに素な正整数 $\ell, m$ に対して $g(\ell m)=g(\ell)g(m)$ が成り立つ関数）であるから， $$\begin{aligned} n\sum_{d\mid n}\frac{\phi(d)}{d} &= n\prod_{p|n}\sum_{k=0}^{\mathrm{ord}_ p(n)}\frac{\phi(p^k)}{p^k} \\ &= n\prod_{p|n}\left(1+\sum_{k=1}^{\mathrm{ord}_ p(n)}\frac{p-1}{p}\right) \\ &= n\prod_{p|n}\frac{(p-1)\mathrm{ord}_ p(n)+p}{p} \\ &= \prod_{p|n} p^{\mathrm{ord}_ p(n)-1}\big((p-1)\mathrm{ord}_ p(n)+p\big) \end{aligned}$$ となる．ここで $p$ が奇素数のとき，$p^{\mathrm{ord}_ p(n)-1}\big((p-1)\mathrm{ord}_ p(n)+p\big)$ は奇数になるから，

$$\mathrm{ord}_ 2(f(n))=\mathrm{ord}_ 2(\mathrm{ord}_ 2(n)+2)+\mathrm{ord}_ 2(n)-1$$

となる．いま $e=\mathrm{ord}_ 2(n)+2$ とおくと問題文の条件は

$$\mathrm{ord}_ 2(e)+e=2^{2023}+2059$$

と同値である．$e\leq2^{2023}$ のとき，$\mathrm{ord}_ 2(e)+e\le2023+2^{2023}$ より不適である．$e\gt2^{2023}$ のとき，$e=2^{2023}+2059-t$（ $t$ は $2059$ 未満の非負整数）とおくと，$\mathrm{ord}_ 2(2059-t)=t$ より $t=0,1,3,11$，すなわち $e=2^{2023}+2048+k$（ $k=0,8,10,11$ ）のとき適することがわかる．
　以上より，$\mathrm{ord}_ 2(f(n))=2^{2023}+2056$ の必要十分条件は $\mathrm{ord}_ 2(n)=2^{2023}+2046+k$（ $k=0,8,10,11$ ）が成り立つことである．これを満たす正整数 $n$ は周期的であることに留意して，$10000$ 番目に小さい正整数 $n$ は $19891\times2^{2^{2023}+2046}$ と求まる．よって，求めるべき値は $19891+2^{2023}+2046\equiv\mathbf{876}\pmod{1009}$ である．