整数論の問題

正の整数 $n$ に対し、$\lfloor \frac{2024}{n}\rfloor$ は $1$ 以上 $2024$ 以下の $n$ の倍数の個数に等しい。よって
$$S=\sum _{n=1}^{2024}\phi (n)\sum _{\begin{array}{c}1\le k\le 2024\\ n\mid k\end{array}}1=\sum _{k=1}^{2024}\sum _{n\mid k}\phi (n)$$
と和の順序を交換できる（$n\mid k$, $k\le 2024$ なら $n\le 2024$ は自動的に成り立つ）。

ここで、よく知られた等式 ${\sum }_{n\mid k}\phi (n)=k$ を用いる（$1,2,\dots ,k$ を $\gcd (j,k)=k/n$ の値で分類すると、各類の個数が $\phi (n)$ になることから従う）。したがって
$$S=\sum _{k=1}^{2024}k=\frac{2024\cdot 2025}{2}=1012\cdot 2025=2049300.$$

$N=2024$ とする。${\sum }_{d\mid k}\phi (d)=k$ を用いる。

$$\sum _{k=1}^{N}k=\sum _{k=1}^N\sum _{d\mid k}\phi (d)=\sum _{d=1}^N\phi (d)\cdot \#\{k\le N:d\mid k\}=\sum _{d=1}^N\phi (d)\lfloor \frac{N}{d}\rfloor .$$

よって $S=\frac{N(N+1)}{2}=\frac{2024\cdot 2025}{2}=1012\cdot 2025=2025000+24300=2049300$。

確かめ（小さい $N$）: $N=4$ で $\phi (1)\cdot 4+\phi (2)\cdot 2+\phi (3)\cdot 1+\phi (4)\cdot 1=4+2+2+2=10=\frac{4\cdot 5}{2}$ ✓。