Estonian Mathematical Olympiad

Note that $1+2+\dots+k = \frac{k(k+1)}{2}$.

a) Since $n$ is odd, the number $\frac{k(k+1)}{2}$ is divisible by $n$ if and only if $k(k+1)$ is divisible by $n$.

Since $2023 = 7 \cdot 17^2$, the number $n$ can be expressed as $p_1^{\alpha_1} p_2^{\alpha_2}$, where $p_1 = 7$, $p_2 = 17$ and $\alpha_1, \alpha_2$ are positive integers. The number $k(k+1)$ is divisible by $n$ iff $k(k+1)$ is divisible by $p_1^{\alpha_1}$ and $p_2^{\alpha_2}$. Since $k$ and $k+1$ have no common factor, their product is divisible by $p_i^{\alpha_i}$ iff one of the factors is divisible by this number. If $k$ is divisible by $p_i^{\alpha_i}$ then $k \equiv 0 \pmod{p_i^{\alpha_i}}$, if $k+1$ is divisible by $p_i^{\alpha_i}$ then $k \equiv -1 \pmod{p_i^{\alpha_i}}$.

By Chinese Remainder Theorem the congruence system
$$\begin{cases} k \equiv d_1 \pmod{p_1^{\alpha_1}} \\ k \equiv d_2 \pmod{p_2^{\alpha_2}} \end{cases}$$
has exactly one solution in the interval $1 \le k \le p_1^{\alpha_1} \cdot p_2^{\alpha_2} = n$ for any integers $d_1$ and $d_2$. The solution $k$ satisfies the conditions of the problem iff $d_1, d_2 \in \{0, -1\}$. There are 4 ways to choose such a vector of the right hand sides, each of them gives a different solution $k$.

b) The number $\frac{k(k+1)}{2}$ is divisible by $n$ iff $k(k+1)$ is divisible by $2n$.

Since $2024 = 2^3 \cdot 11 \cdot 23$, the number $n$ can be expressed as $2^{\beta_0} q_1^{\beta_1} q_2^{\beta_2}$, where $q_1 = 11$, $q_2 = 23$ and $\beta_0, \beta_1, \beta_2$ are positive integers. The number $k(k+1)$ is divisible by $2n$ iff $k(k+1)$ is divisible by $2^{\beta_0+1}$, $q_1^{\beta_1}$ and $q_2^{\beta_2}$. Since $k$ and $k+1$ have no common factor, their product is divisible by each of the powers of the primes iff one of the factors is divisible by this number. So $k(k+1)$ is divisible by $2^{\beta_0+1}$ iff $k \equiv 0 \pmod{2^{\beta_0+1}}$ or $k \equiv -1 \pmod{2^{\beta_0+1}}$, and by $q_i^{\beta_i}$ ($i \in \{1, 2\}$) iff $k \equiv 0 \pmod{q_i^{\beta_i}}$ or $k \equiv -1 \pmod{q_i^{\beta_i}}$.

By Chinese Remainder Theorem the congruence system
$$\left\{ \begin{array}{ll} k \equiv d_0 & (\text{mod } 2^{\beta_0}) \\ k \equiv d_1 & (\text{mod } q_1^{\beta_1}) \\ k \equiv d_2 & (\text{mod } q_2^{\beta_2}) \end{array} \right.$$
has exactly one solution in the interval $1 \le k \le 2^{\beta_0} \cdot q_1^{\beta_1} \cdot q_2^{\beta_2} = n$ for any integers $d_0, d_1$ and $d_2$. The solution $k$ satisfies the conditions of the problem iff $d_0, d_1, d_2 \in \{0, -1\}$ and $k \equiv d_0 \pmod{2^{\beta_0+1}}$. Note that if $d_0 = d_1 = d_2 = 0$ then $k = n \ne 0 \pmod{2^{\beta_0+1}}$, and if $d_0 = d_1 = d_2 = -1$ then $k = n - 1 \ne -1 \pmod{2^{\beta_0+1}}$. Otherwise let $d'_i = -1 - d_i$ and define $k'$ as the solution of the congruence system
$$\left\{ \begin{array}{ll} k' \equiv d'_0 & (\text{mod } 2^{\beta_0}) \\ k' \equiv d'_1 & (\text{mod } q_1^{\beta_1}) \\ k' \equiv d'_2 & (\text{mod } q_2^{\beta_2}) \end{array} \right.$$
in the interval $1 \le k' \le n$. Note that $k + k' \equiv -1 \pmod{n}$; since $1 \le k, k' \le n-2$, we have $-1 < k + k' < 2n-1$, hence $k + k' = n-1$. Also note that $k \equiv d_0 \pmod{2^{\beta_0}}$ means that exactly one of claims $k \equiv d_0 \pmod{2^{\beta_0+1}}$ and $k \equiv n+d_0 \pmod{2^{\beta_0+1}}$ is true, the same holds for $k'$. It follows that exactly one of claims $k \equiv d_0 \pmod{2^{\beta_0+1}}$ and $k' \equiv d'_0 \pmod{2^{\beta_0+1}}$ is true. Indeed, if both were true then $n-1 = k+k' \equiv d_0+d'_0 = -1 \pmod{2^{\beta_0+1}}$, if neither of them were valid, then $n-1 = k+k' \equiv 2n+d_0+d'_0 = 2n-1 \pmod{2^{\beta_0+1}}$ – a contradiction in both cases. Consequently there are $\frac{8-2}{2} = 3$ integers satisfying the conditions.