2020 OIM Problems/Problem 2

Problem

For each positive integer $n$, define $T_n$ as the smallest positive integer such that $1 + 2 + \cdots + T_n$ is a multiple of $n$. For example, $T_5 = 4$ since $1$, $1 + 2$ and $1 + 2 + 3$ are not multiples of $5$, but $1 + 2 + 3 + 4$ is a multiple of $5$. Find all positive integers $m$ such that $T_m \ge m$.

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

Note the elementary property that will be used without proof: for all positive integers $n$, \[1+2+\cdots+n=\frac{1}{2}n(n+1)\]

We claim that the only possible $m$ are numbers of the form $\boxed{2^x}$, where $x$ is a nonnegative integer. First, we show that these numbers do in fact satisfy the condition. By formula, we have $\frac{1}{2}T_n(T_n+1)=2^x$; thus $T_n(T_n+1)=2^{x+1}$. Only one of $T_n$ or $T_n+1$ is even.

If $T_n$ is even, then we must have $2^{x+1}|T_n$, which is clearly only possible if $T_n\ge2^{x+1}>2^{x+1}-1$. If $T_n+1$ is even, then we must have $T_n+1\ge2^{x+1}$; thus $T_n\ge2^{x+1}-1$. For all nonnegative $x$, it is easily shown that $2^{x+1}-1\ge2^x$; thus, \[T_n\ge2^{x+1}-1\ge2^x=m\] so these $m$ satisfy the condition regardless of the parity of $T_n$.

Next, we show that these are the only possible $m$. First, assume that $m=p^k$ such that $p$ is an odd prime and $k$ is a positive integer. Clearly if $T_m=m-1$, then the property is satisfied (although this may not be minimal) since we must have $2|(m-1)$; thus these cases are eliminated. Then consider $m$ as any other odd number. Let $m=ab$ for relatively prime odd integers $a,b>1$; this is possible since we already considered odd $m$ with only one prime factor. Consider all nonnegative integers $\alpha$ such that \[\alpha\equiv0\pmod{a}\] \[\alpha\equiv-1\pmod{b}\]

By the Chinese Remainder Theorem, there exists some $\alpha\in[0,ab-1]$ such that the above holds. Clearly $\alpha=0$ does not work, so there exists some unique $\alpha\in[1,m-1]$; let this be $\alpha_0$. Notice that $\frac{1}{2}\alpha_0(\alpha_0+1)$ would then be divisible by $m=ab$, so $T_n=\alpha_0$ would satisfy the property (although it may not be minimized); thus we must have $T_n\le\alpha_0<m$, eliminating this case.

Finally, we consider even $m$. Let $m=2^y\cdot t$ for positive integers $y,t$ such that $t\ne1$ is odd (because we already showed that $t=1$ works). Then $2^y$ and $t$ are clearly relatively prime.

Let $\beta_1,\beta_2$ be nonnegative integers in the interval $[1,2^{y+1}t-1]$ such that \[\beta_1\equiv0\pmod{2^{y+1}}\] \[\beta_1\equiv-1\pmod{t}\] \[\beta_2\equiv-1\pmod{2^{y+1}}\] \[\beta_2\equiv0\pmod{t}\]

Again, since $\beta_1=0$ or $\beta_2=0$ clearly do not satisfy the above, then by the Chinese Remainder Theorem, there will always exist some unique integers $\beta_1,\beta_2$ in the interval $[1,2^{y+1}t-1]$, so we are able to define them as such above. Next, adding the first/third congruences and the second/fourth congruences: \[\beta_1+\beta_2\equiv-1\pmod{2^{y+1}}\] \[\beta_1+\beta_2\equiv-1\pmod{t}\] Notice that \[\beta_1+\beta_2\equiv-1\pmod{2^{y+1}t}\] satisfies this system of congruences; by the Chinese Remainder Theorem, this solution is unique. Thus, \[\beta_1+\beta_2+1\equiv0\pmod{2^{y+1}t}\] However, since $\beta_1,\beta_2\in[1,2^{y+1}t-1]$, this implies that $\beta_1+\beta_2+1\in[3,2\cdot2^{y+1}-1]$. From the above congruence, the only multiple of $2^{y+1}t$ in this interval is $2^{y+1}t$ itself; thus, \[\beta_1+\beta_2+1=2^{y+1}t\] \[\Rightarrow\beta_1+\beta_2=2^{y+1}t-1\] Assume for the sake of contradiction that both $\beta_1,\beta_2\ge2^yt$. Then $\beta_1+\beta_2\ge2^{y+1}t$, clearly a contradiction. Thus at least one of $\beta_1,\beta_2<2^yt$, implying that at least one of $\beta_1,\beta_2<m$. Assume that $\beta_1<m$; then $\frac{1}{2}\beta_1(\beta_1+1)$ is divisible by $m=2^yt$ from our congruences above, so setting $T_n=\beta_1$ would suffice; thus $T_n\le\beta_1<m$; the same goes for $\beta_2$ if $\beta_2<m$. As a result, this case is also eliminated, so we are done.

~ eevee9406

See also

OIM Problems and Solutions