Estonian Mathematical Olympiad

Note that $1+2+\cdots +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(\mathrm{mod}{p}_i^{{\alpha }_i})$, if $k+1$ is divisible by $p_i^{{\alpha }_i}$ then $k\equiv -1(\mathrm{mod}{p}_i^{{\alpha }_i})$.

By Chinese Remainder Theorem the congruence system $$\{\begin{array}{l}k\equiv d_1(\mathrm{mod}{p}_1^{{\alpha }_1})\\ k\equiv d_2(\mathrm{mod}{p}_2^{{\alpha }_2})\end{array}$$ 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(\mathrm{mod}{2}^{{\beta }_0+1})$ or $k\equiv -1(\mathrm{mod}{2}^{{\beta }_0+1})$, and by $q_i^{{\beta }_i}$ ($i\in \{1,2\}$) iff $k\equiv 0(\mathrm{mod}{q}_i^{{\beta }_i})$ or $k\equiv -1(\mathrm{mod}{q}_i^{{\beta }_i})$.

By Chinese Remainder Theorem the congruence system $$\{\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}$$ 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(\mathrm{mod}{2}^{{\beta }_0+1})$. Note that if $d_0=d_1=d_2=0$ then $k=n\ne 0(\mathrm{mod}{2}^{{\beta }_0+1})$, and if $d_0=d_1=d_2=-1$ then $k=n-1\ne -1(\mathrm{mod}{2}^{{\beta }_0+1})$. Otherwise let $d_i^{\prime }=-1-d_i$ and define $k^{\prime }$ as the solution of the congruence system $$\{\begin{array}{ll}{k}^{\prime }\equiv d_0^{\prime }& (\text{mod }{2}^{{\beta }_0})\\ k^{\prime }\equiv d_1^{\prime }& (\text{mod }{q}_1^{{\beta }_1})\\ k^{\prime }\equiv d_2^{\prime }& (\text{mod }{q}_2^{{\beta }_2})\end{array}$$ in the interval $1\le k^{\prime }\le n$. Note that $k+k^{\prime }\equiv -1(\mathrm{mod}n)$; since $1\le k,k^{\prime }\le n-2$, we have $-1<k+k^{\prime }<2n-1$, hence $k+k^{\prime }=n-1$. Also note that $k\equiv d_0(\mathrm{mod}{2}^{{\beta }_0})$ means that exactly one of claims $k\equiv d_0(\mathrm{mod}{2}^{{\beta }_0+1})$ and $k\equiv n+d_0(\mathrm{mod}{2}^{{\beta }_0+1})$ is true, the same holds for $k^{\prime }$. It follows that exactly one of claims $k\equiv d_0(\mathrm{mod}{2}^{{\beta }_0+1})$ and $k^{\prime }\equiv d_0^{\prime }(\mathrm{mod}{2}^{{\beta }_0+1})$ is true. Indeed, if both were true then $n-1=k+k^{\prime }\equiv d_0+d_0^{\prime }=-1(\mathrm{mod}{2}^{{\beta }_0+1})$, if neither of them were valid, then $n-1=k+k^{\prime }\equiv 2n+d_0+d_0^{\prime }=2n-1(\mathrm{mod}{2}^{{\beta }_0+1})$ – a contradiction in both cases. Consequently there are $\frac{8-2}{2}=3$ integers satisfying the conditions.