Notice the problem is equivalent to find all $m$ such that $f(x)=\frac{x^2+x}{2}\equiv 0\mod m$ has no a non trivial solution i.e there is a solution $r\not\equiv 0\mod m$ which satisfy the relation, contradiction. If $m$ is odd we have $\gcd(m,2)=1$ so $$2f(x)\equiv 0\mod m$$which has a solution $x=m-1$ so $T_m\le m-1$ there are no odd solutions. Thus $m$ must be of the form $m=2^k\prod_{i=1}^{\omega(m)-1} p_i^{\nu_{p_i}(m)}$. If $\omega(m)>1$ we have at least a prime satisfying $$f(x)\equiv 0\mod p_i^{\nu_{p_i}(m)}$$And this has two roots so by $CRT$ we have at least $2$ distinct solutions for $x$ after considering the system of relatively primes $$f(x)\equiv 0\mod 2^k$$$$f(x)\equiv 0\mod p_i^{\nu_{p_i}(m)}$$But this implies there is a non-trivial solution and we are done, this can't be a solution. So $m=2^k$. The converse is quite easy to check, suppose $m=2^k$ is satisfying $$\frac{T_m(T_m+1)}{2}\equiv 0\mod 2^k\implies T_m(T_m+1)\equiv 0\mod 2^{k+1}$$And since $\gcd(T_m,T_m+1)=1$ we have either $2^{k+1}\mid T_m$ or $2^{k+1}\mid T_m+1$ the first implies $$T_m\ge 2^{k+1}>2^k$$And the later implies $$T_m\ge 2^{k+1}-1\ge 2^{k+1}-2^k=2^k$$So we are done, we showed all the solutions are $m=2^k\forall k\in\mathbb N\cup \{0,\}$.

This problem was proposed by Colombia by me (Nicolás De la Hoz).

If $m=2^a$ clearly $T_m>m$. Let $m=2^a(2k+1)$, with $k\geq 1$. Consider the set $S=\{2^{a+1}, 2\cdot 2^{a+1},\dots,k\cdot 2^{a+1}\}$. Notice that every element of the set is strictly smaller than $m$. Easy to check that: * mod $(2k+1)$, the $k$ elements of $S$ are different. * mod $(2k+1)$, at most one of the elements of the tuple $(x,2k+1-x)$ belongs $S$. Conclusion: From each tuple in $\{(1,2k),(2,2k-1),\dots,(k,k+1)\}$ we have exactly one element in $S$. Then there exist $1\leq b\leq k$ such that either $b\cdot 2^{a+1}-1\equiv 0(2k+1)$ or $b\cdot 2^{a+1}+1\equiv 0(2k+1)$. Case 1: $b\cdot2^{a+1}-1\equiv 0(2k+1)$. Clearly $\frac{(b\cdot 2^{a+1}-1)(b\cdot 2^{a+1})}{2}$ is divisible by $m=2^a(2k+1)$, then $T_m\leq b\cdot 2^{a+1}-1\leq 2^a(2k+1)=m$ . Case 2: $b\cdot 2^{a+1}+1\equiv 0(2k+1)$. Clearly $\frac{(b\cdot 2^{a+1})(b\cdot 2^{a+1}+1)}{2}$ is divisible by $m=2^a(2k+1)$, then $T_m\leq b\cdot 2^{a+1}\leq 2^a(2k+1)=m$. Then the answer is every $m$ but the powers of $2$.

The gist is essentially to analyze the case when $m=2^{\alpha}\cdot m'$, $k\ge 1$, and $m'>1$ odd (the rest, case when $m$ is odd and $m$ is a power of two are both quite trivial). For this case, I think my solution below is instructive and clear: Consider two congruences: \[ \mathcal{C}_1 : \quad x\equiv 0\pmod{2^{\alpha+1}} \quad\text{and}\quad x\equiv -1\pmod{m'}. \]\[ \mathcal{C}_2 : \quad x\equiv -1\pmod{2^{\alpha+1}} \quad\text{and}\quad x\equiv 0\pmod{m'}. \]By the CRT, both $\mathcal{C}_1$ and $\mathcal{C}_2$ have a solution modulo $2^{\alpha+1}m'=2m$. I claim it is the case that the smallest solution to one of them is less than or equal to $m$. For that, let $\ell m'-1$ be the smallest positive solution to $\mathcal{C}_1$. In particular, $\ell m'\equiv 1\pmod{2^{\alpha+1}}$. If $\ell m'-1 \le m$, we are done. Otherwise, assume $\ell m'-1>m$. We have \[ 2m>\ell m'>m \implies 2^{\alpha+1}>\ell >2^\alpha. \]Consider now the number \[ x = \left(2^{\alpha+1}-\ell\right) m' = 2m - \ell m'. \]Clearly $x<m$, and $x$ is divisible by $m'$. Furthermore, $x\equiv -1\pmod{2^{\alpha+1}}$. Therefore, $x<m$ solves the congruence $\mathcal{C}_2$. This concludes the proof.

Iberoamerican Math Olympiad 2020 P2 wrote: Let $T_n$ denotes the least natural such that $$n\mid 1+2+3+\cdots +T_n=\sum_{i=1}^{T_n} i$$Find all naturals $m$ such that $m\ge T_m$. Proposed by Nicolás De la Hoz Somewhat similar to @above, I think. Suppose firstly that $m$ is a power of $2$. Let $m=2^k$. We must have $2^{k+1} \mid T_m(T_m+1)$, hence $2^{k+1} \mid T_m$ or $2^{k+1} \mid T_m+1$. In both cases, $T_m \geq 2^{k+1}_1 >2^k=m$, therefore all powers of $2$ don't satisfy. Suppose now $m$ is not a power of $2$. Let $m=2^P Q$ with $Q>1$ odd. We prove now the following Claim, which gives the result. Claim: Let $s,t$ be minimal such that $2^{P+1} \mid (s+1), \, Q \mid s$ and $2^{P+1} \mid t, \, Q \mid (t+1)$. Then, either $s$ or $t$ is $<2^PQ$. This Claim instantly solves the problem, since if for example $s<2^PQ$, then we have $2^{P+1}Q \mid s(s+1)$, hence $2^PQ=m \mid 1+2+\ldots+s$, therefore $m=2^PQ>s \geq T_m$, hence we are done. What remains is to prove the Claim. Proof: Let $s=2^{P+1}B-1$ and $t=2^{P+1}A$. Then, we have $Q \mid (2^{P+1}B-1)$ and $Q \mid (2^{P+1}A+1)$. Note that by CRT and the minimal condition we have $t,s \leq 2^{P+1}Q,$ therefore $A,B \leq Q$. In addition, $$2^{P+1}(Q-B)+1 \equiv -2^{P+1}B+1 \equiv 0 \pmod Q$$hence we must have $Q-B \geq A$, since $t$, and subsequently $A$, is minimal. Therefore $A+B \leq Q$, implying that either $A$ or $B$ is $\leq Q/2$. Suppose $A \leq Q/2$. Then $t=2^{P+1}A \leq 2^PQ=m$, as desired. Similarly we conclude if $B \leq Q/2$. $\blacksquare$.

grupyorum wrote: The gist is essentially to analyze the case when $m=2^{\alpha}\cdot m'$, $k\ge 1$, and $m'>1$ odd (the rest, case when $m$ is odd and $m$ is a power of two are both quite trivial). For this case, I think my solution below is instructive and clear: Consider two congruences: \[ \mathcal{C}_1 : \quad x\equiv 0\pmod{2^{\alpha+1}} \quad\text{and}\quad x\equiv -1\pmod{m'}. \]\[ \mathcal{C}_2 : \quad x\equiv -1\pmod{2^{\alpha+1}} \quad\text{and}\quad x\equiv 0\pmod{m'}. \]By the CRT, both $\mathcal{C}_1$ and $\mathcal{C}_2$ have a solution modulo $2^{\alpha+1}m'=2m$. I claim it is the case that the smallest solution to one of them is less than or equal to $m$. For that, let $\ell m'-1$ be the smallest positive solution to $\mathcal{C}_1$. In particular, $\ell m'\equiv 1\pmod{2^{\alpha+1}}$. If $\ell m'-1 \le m$, we are done. Otherwise, assume $\ell m'-1>m$. We have \[ 2m>\ell m'>m \implies 2^{\alpha+1}>\ell >2^\alpha. \]Consider now the number \[ x = \left(2^{\alpha+1}-\ell\right) m' = 2m - \ell m'. \]Clearly $x<m$, and $x$ is divisible by $m'$. Furthermore, $x\equiv -1\pmod{2^{\alpha+1}}$. Therefore, $x<m$ solves the congruence $\mathcal{C}_2$. This concludes the proof. Why do you have $2m > \ell \cdot m'$ ?

Here is my solution, which I will present in two important lemmas: $\textbf{Lemma 1.}$ There does not exist $T_{n}$ for $n=2^k$ such that it is smaller than $n$. Proof: $1+2+3+\cdots+n=\frac{n(n+1)}{2}$, so $2^k\mid \frac{T_{2^k}(T_{2^k}+1)}{2}$ implies that $2^{k+1}\mid T_{2^k}(T_{2^k}+1)$ so $T_{2^k}\geq2^{k+1}-1>2^k$, contradiction! $\textbf{Lemma 2.}$ For all numbers $n=2^{k}m$, with $m$ being odd and larger than $1$, $T_{n}\leq n$. Proof: When $k$ $=$ $0$ just put $m-1$, it satisfies given condition. When $k\geq 1$ put $T_{n}=2^{k+1}x$ or $T_{n}=2^{k+1}x-1$ and we will find suitable $x\leq \frac{m}{2}$. So if $2^{k}m\mid \frac{2^{k+1}x(2^{k+1}x+1)}{2}$ or $2^{k}m\mid \frac{2^{k+1}x(2^{k+1}x-1)}{2}$ it implies that $m\mid x(2^{k+1}x+1)$ or $m\mid x(2^{k+1}x-1)$, and now we will look at the system of congruences $2^{k+1}x\equiv -1 mod $ $m$ and $2^{k+1}x \equiv 1 mod $ $m$ and finding one solution $x$ such that it is congruent to number that is smaller than $\frac{m}{2}$ will prove the lemma since we can just pick that number and it will satisfy all conditions. Now we reduce all numbers $mod$ $m$ and look at the solution to $2^{k+1}x_{1}\equiv 1$, that solution will definitely exist because $gcd(2^{k+1},m)=1$ since m is odd. And if $x_{1}>\frac{m}{2}$ then we can just pick $x_{2}=m-x_{1}< \frac{m}{2}$ and it satisfies all conditions, proving our lemma.

Al3jandro0000 wrote: Let $T_n$ denotes the least natural such that $$n\mid 1+2+3+\cdots +T_n=\sum_{i=1}^{T_n} i$$Find all naturals $m$ such that $m\ge T_m$. Proposed by Nicolás De la Hoz As $\sum_{i=1}^{T_n} i=\frac{T_n(T_n+1)}{2}$ Now as $\frac{T_m(T_m+1)}{2m}\in N$ and let $m=2^k*y$ for some $y,k\in N$ then we have $2^{k+1}*y|T_m(T_m+1)$ Now as $gcd(T_m, T_m+1)=1$ so either $2^{k+1}*x=T_m$ or $2^{k+1}*x-1=T_m$ then we also have $y|x(2^{k+1}x-1)$ or $y|x(2^{k+1}x+1)$ Now as we need $2^{k+1}*y\geq T_m$ Claim 1-: $y\neq 2^z$ for any $z\in N$ We will asume the contrary so let $y=2^z$ then we have $2^z|x(2^{k+1}x +1)$ or $2^z|x(2^{k+1}x+1)\implies 2^z|x$ hence $T_m=2^{z+k+1}*x_1$ or $2^{k+z+1}*x_1-1>2^{k+z}=m$ which is contradiction. Hence $2^k$ is the maximum of $2$ which divide $m$ or $v_2(m)=k$ and so let $m=2^k*y_1$ for some odd $y$. Claim 2-: for all odd $y_1$ where $m=2^k*y_1$ will satisfy the condition. So we have to prove that there always exist $x$ such that $x<\prod_{i=1}^{m-1} p_i$ and $y=\prod_{i=1}^{m}p_i$ for prime $p_i$ such that $p_m>p_{m-1}>....>p_1>2$ for some $m\in N$ we have $y_1|x(2^{k+1}x+1)$ or $y_1|x(2^{k+1}x-1)$ so either $x(2^{k+1}x-1)\equiv 0\mod y_1$ or $x(2^{k+1}x+1)\equiv 0\mod y_1$ as $x<y$ so we must need to prove $2^{k+1}x\equiv \pm 1\mod p_n$ for some $p_n|y,p_n\nmid x$ and $n<m$ which is clearly true as by property of mods as $gcd(2^{k+1}x, p_n)|\pm 1$ so there will always exist exactly one $x<p_n$ so we are done. $\blacksquare$

Ok so for some reason I solved the opposite problem, so I'll rephrase the problem here so that my solution makes sense: Al3jandro0000 wrote: Let $T_n$ denotes the least natural such that $$n\mid 1+2+3+\cdots +T_n=\sum_{i=1}^{T_n} i$$Find all naturals $m$ such that $T_m > m$. Proposed by Nicolás De la Hoz The answer is $2^n$ for positive integers $n$ and $0$. We first show that these do work, and then we show that the others don't work. $1$ trivially works. Now we assume that $n$ is positive. For convenience, let $T_n=x$. Then notice that the condition is basically just that no $x\leq n$ satisfy $\nu_2(\frac{x(x+1)}{2})\geq n$. Notice that for it to satisfy the equation, $x=2^n-1$ or $x=2^n$, so that the numerator at least has an $\nu_2$ values $\geq n$. However, it is easy to see the division by $2$ causes both of these too fail, so we have showed that these solutions work. We now show that no other numbers work. First off, it is clear that no odd number works, as for any odd $k,$ $k-1$ works, so $T_k\leq k-1,$ already strong enough to prove the claim. Now, to finish, we just show that any odd number multiply by any power of $2$ also does not work. This would be strong enough to prove the claim. Notice that this condition is basically equivalent to $kc\pm 1\equiv 0\pmod 2^{d+1},$ for whatever power of $2$ you are trying to multiply by(we have to add one to the $\nu_2$ because of the division by $2$). Then it is easy to see that the solutions for $c$ are just $\pm k^{-1},$ and $k^{-1}$ exists because it is odd, coprime with modulus. Clearly, at least one of these $\leq 2^d$(the two halves of the residue class each contain one of $k^{-1}$ or $-k^{-1}$, and notice there is no "single middle" issue because the number of elements in the $2^{d+1}$ residue class is even), so we are done.

(this solution is for $m \geq T_m$ instead of $m< T_m$)

The answer is all positive integers. In particular, we just need an integer $k \leq n$ such that $$2n \mid k(k+1).$$We will show that there must exist such a $k \leq n$ such that \begin{align*} k+1 &\equiv 0 \pmod {2^{\nu_2(n)+1}} \\ k+1 &\equiv 1 \pmod {\tfrac n{\nu_2(n)}}. \end{align*}or vice versa. Because the two mods are relatively prime, we know there exists some $k \leq 2n$ such that this is true. If this $k \leq n$, we are done. If $k \geq n$, then consider the number $2n-k$. First, $$2n-k \equiv 0 - (-1) \equiv 1 \pmod {2^{\nu_2(n)+1}},$$whilst $$2n-k \equiv 0 - 0 \equiv 0 \pmod {\tfrac n{\nu_2(n)}},$$and thus satisfies the ``vice versa" system of congruences. We also know that $2n-k \leq n$ -- thus the claim is true as desired.

Oops, I solved also the opposite problem just as JustKeepRunning did. Rephrased IberoAmerican 2020 P2 wrote: Let $T_n$ denotes the least natural such that $$n\mid 1+2+3+\cdots +T_n=\sum_{i=1}^{T_n} i$$Find all naturals $m$ such that $T_m > m$. I claim that the answer is $2^k$ for all $k\geq 1$. Firstly, we simplify the given, $$n\mid \sum_{i=1}^{T_n} i =\frac{T_n(T_n+1)}{2}\implies T_n(T_n+1)\equiv 0\pmod{2n}.$$ For the numbers in the form $n=2^k$, we must have $$T_n(T_n+1)\equiv 0 \pmod{2^{k+1}}$$and as $\gcd(T_n,T_n+1)=1$, we must have either $2^{k+1}\mid T_n$ or $2^{k+1}\mid T_n+1$, thus $T_n=2^{k+1}-1=2n-1>n$. For all the odd numbers $m$ note that $m$ works, thus definitely $m\geq T_m$ for any odd. Claim. For any odd $s$, there exists odd $x<2^{l}$ such that $xs\pm 1\equiv 0\pmod{2^{l+1}}$, where $l\geq 1$. Proof. Take any $x_1,x_2<2^{l}$. Firstly note that if $x_1s\pm 1\equiv x_2s\pm 1\equiv 0\pmod{2^{l+1}}$, then $x_1\equiv x_2\pmod{2^{l+1}}$, which implies that $x_1=x_2$. This essentially means that as $x$ varies, $xs\pm1$ give different residues mod $2^{l+1}$, similarly $xs\pm 1$ is injective over $F_{2^{l}}$. Now take $x_1,x_2<2^{l}$ and consider $x_1s\pm 1\equiv x_2s\mp 1\equiv 0\pmod{2^{l+1}}$, which implies that $(x_1-x_2)s\pm 2\equiv 0\pmod{2^{l+1}}$. But note that this implies a contradictions as if $4\mid x_1-x_2$, we get that $4\mid 2$ as $l\geq 1$, which is impossible. But if $x_1-x_2=2k$ for some odd $k$, we get that $ks\pm 1\equiv 0\pmod{2^{l}}$, which contradicts that fact that $xs\pm 1$ is injective over $F_{2^{l}}$. Therefore, all $xs\pm 1\equiv 0\pmod{2^{l+1}}$ imply different values of $s$, and, as we have $2^{l}$ different congruences, we obtain $2^{l}$ different odd values of $s$, the claim follows. $\square$ Consider numbers in the form $n=2^ls$, where $l\geq 1$ and $s$ is any odd number. By the claim, we get that for any odd $s$, there exists odd $x<2^{l}$ such that $xs\pm 1\equiv 0\pmod{2^{l+1}}$, thus either $xs-1$ or $xs$ works, where both are smaller than $n=2^ls$, we are done.

The answer is all $m$ except for the powers of 2, as well as 1. Clearly 1 works. Let $f(n)=\sum_{i=1}^{n}i$, and suppose $m=2^k$ for $k\ge 1$. Assume for the sake of the contradiction that there existed an even solution $a\le m$. Then $\nu_2(a)\le k$, and $\nu_2(a+1)=0$. Clearly $\nu_2(f(a))\le k+0-1=k-1$, and therefore $m$ cannot divide the sum. Now assume for the sake of contradiction that there existed an odd solution $a$. Then $\nu_2(a)=0,$ and $\nu_2(a+1)\le n$. Repeat. Now suppose $m=2^k(a)$ for odd $c>1$. Let $a\pmod{2^{k+1}}=b$. It is clear that one of $\tfrac 1b$ and $-\tfrac 1b \pmod{2^{k+1}}$ is less than $2^k$. Let $c$ be this value. If $c=\tfrac 1b$, then $ac-1$ is a valid solution since it is less than $m$ and $f(ac-1)=\tfrac{(ac-1)(ac)}{2}$ which is clearly divisible by both $a$ and $2^k$ since $ac\equiv b\cdot \tfrac 1b=1\pmod {2^{k+1}}$. If $c=-\tfrac 1b$, then $ac$ is a valid solution by the same reasoning. We have shown that powers of 2 greater than 1 don't work, and every other number works, so we are done.

We claim that all $m$ works except for when $m$ is a power of two and is greater than $1$. Claim 1. All odd $m$ works. Proof. We know that $T_m=m$ works, but this might not be the smallest, so we have \[ T_m \le m \implies m \ge T_m. \] Claim 2. $m=1$ works. Proof. Obvious. If you don't understand why this is true, stop reading this solution and go to first grade, please. Claim 3. When $m$ is a power of two, it doesn't satify the condition. Proof. Notice that the condition implies that there exists a positive integer $a$ such that $a(a+1)=2m$. Now if $a$ is even, then $a+1$ is odd which means $\nu_2(a+1)=0$. So $\nu_2(a)+\nu_2(a+1)=\nu_2(a)$. Now let $m=2^b$ and so $\nu_2(2m)=b+1$. Also notice that $\nu_2(a) \le b$ because $a\le m$, and hence a contradiction. The case when $a$ is odd, and $a+1$ is even follows the same logic and we are done. Claim 4. All $m$ that is even and not a power of two work. Proof. Let \begin{align*} a&=2^{\nu_2(m)+1} \\ b&=\frac{m}{2^{\nu_2(m)}} \end{align*}Now if $a>b$, let $a\equiv x\pmod{b}$. Then let $y$ be the modular inverse of $a \mod b$. This means that $ay \equiv 1 \pmod{b}$ and $0<y<b$. Because we know $0<y<b$, we know that $ay<2m$. Now if $ay\le m$ then we can have $T_m=ay-1$ and we would be done. Now if $ay>m$ then we consider the number $2n-ay$. Notice that \begin{align*} 2n-ay \equiv 1 \pmod{b} \\ 2n-ay \equiv 0 \pmod{a} \\ \end{align*}and so we can have $T_m=2n-ay-1$. Using the same proof as above for when $b>a$, we are done.

Answer:$m=2^s(2t+1)$, with $t \geq 1$.

Answer: All positive integers that are not powers of $2$ besides $m=1$. Clearly all odd numbers $n=2k+1$ work as \[n \mid 1+2+3+\ldots+(2k-2)+(2k-1)+2k=(1+2k)+(2+2k-1)+\ldots+(k+k+1)\]so $T_n\le 2k<2k+1=n$. Another way to see this is that $1+2+\ldots+2k=\frac{2k(2k+1)}{2}=k\cdot (2k+1)$. Claim 1. If $n>1$ satisfies $n\ge T_n$, then so does $2n\ge T_{2n}$ hold. Proof claim 1. If $n=2k+1$, with $k$ being odd, then we have \[2n=4k+2\mid 1+2+\ldots+2k+(2k+1)=\frac{(2k+1)(2k+2)}{2}=(2k+1)(k+1)\]as $k+1$ is even, i.e. $T_{2n}\le 2k+1<2n$. Otherwise, if $k$ is even, \[2n=4k+2\mid 1+2+\ldots+2k=k(2k+1)=\frac k2(4k+2)\]i.e. $T_{2n}\le 2k<2n$. $\square$ As we have already checked, all odd numbers work, and with this claim all even multiples of odd numbers work, which are exactly all positive integers that are not powers of $2$. Claim 2: The numbers of the form $n=2^k$, $k>0$ do not satisfy $n\ge T_n$. Proof of claim 2. If $\ell\le n=2^k$ is even then \[\nu_2\left(\frac{\ell(\ell+1)}{2}\right)=\nu_2\left(\frac{\ell}{2}\right)=\nu_2(\ell)-\nu_2(2)=\nu_2(\ell)-1<k.\]so $2^k$ cannot divid this sum. We get the same thing when $\ell$ is odd, as $\nu_2{\ell+1}\le k$ as well, so $\nu_2{\ell+1}-1<k.$ $\square$ This finishes the proof. $\blacksquare$.

We claim the set of solutions is $\mathbb{Z}^+ \setminus \{2^e\mid e>1,~ e\in \mathbb{Z}\}$. If $n=2^e$ for an integer $e\geq 2$, then we need $T_n\geq 2^{e+1}-1$ in order for $\nu_2(\tfrac{1}{2}T_n(T_n+1))$ to be at least $e$, since we need either $2^{e+1}\mid T_n$ or $2^{e+1}\mid T_n+1$. Hence none of the powers of $2$ work (other than $1$). Now suppose that $n=2^e\cdot q$ where $2\nmid q$ and $q>1$ is a positive integer. We want $T_m(T_m+1)\equiv 0\pmod{2^{e+1}}$ and $T_m(T_m+1)\equiv 0\pmod{q}$. Let $q'$ be the inverse of $q \mod 2^{e+1}$. If $q'\leq 2^e$, then we can let $T_n=qq'-1$, since then $2^e\mid \tfrac{1}{2}T_n$ and $q\mid T_n+1$, and furthermore $qq'-1\leq 2^e q-1<n$. If $q'>2^e$, then we can let $T_n=q(2^{e+1}-q')$, since then $q\mid T_n$ and $2^e\mid \tfrac{1}{2}(T_n+1)$, and furthermore $q(2^{e+1}-q')<q\cdot 2^e=n$. Hence all numbers of the form $2^e\cdot q$ work, and we are done.

Nyess poblam orss . I claim that all non-powers of two work. Let $n=2^k\cdot(2m+1)$. We firstly work with $k\ge 1$. Now I claim that there is a multiple of $2^{k+1}$ among the following, \begin{align*} (2m+1)&\cdot 1\pm 1\\ (2m+1)&\cdot 3\pm 1\\ &\vdots\\ (2m+1)\cdot (&2^k-1)\pm 1 .\end{align*} First notice that if our claim is actually true, then we will have our proof simply choosing our $T_n$ as the working choice from the above listed for $-1$, otherwise the $T_n=\text{choice}-1$ for $+1$. Now FTSOC assume that all the ones are non-multiples of $2^{k+1}$. Also notice that all the choices above are even. So we consider their binary representation. So the representation must have its last digit as $0$. Now also notice that all the ones are distinct $\pmod{2^{k+1}}$ which simply follows from a contradiction and some case bashing. Now note that we have at most $2^k-1$ binary representations with $k+1$ digits that are even but are not divisible by $2^{k+1}$ but above, we have $2^{k}$ choices which is a clear contradiction and we are done. For the case $k=0$, note that taking just taking $T_n=n$ works and we are done. Now for the proof that the powers of $2$ don't work, a simple $\nu_{2}$ contradiction works and we are done.

Cool We claim that the answer is $\boxed{\text{all numbers that are not powers of 2 greater than 1.}}$ We will first prove that all such $m$ work. Clearly $m = 1$ works, so assume $m \ne 1.$ Write $m = b \cdot 2^a,$ where $b$ is odd. Obviously $$1 + 2 + \dots + T_n = \frac{T_n (T_n + 1)}{2}.$$Thus we require that $2m| T_m (T_m + 1),$ or, when plugging in values, $2^{a+1} b | T_m (T_m + 1).$ Now, let $p$ be the unique integer between $0$ and $b \cdot 2^{a+1} - 1$ inclusive such that $$p \equiv 0 \pmod{b}$$and $$p \equiv -1 \pmod{2^{a+1}}.$$Such a value for $p$ exists by CRT, and setting $T_m = p$ would work. However, we do not know if $p > b \cdot 2^{a}$ or not. To counter this, we consider the unique integer $q$ between $0$ and $b \cdot 2^{a+1} - 1$ such that $$q \equiv -1 \pmod{b}$$and $$q \equiv 0 \pmod{2^{a+1}}.$$This value of $q$ also exists by CRT, and plugging in $T_m = q$ would also work. We also do not know whether or not $q > b \cdot 2^a.$ The main idea is to add $p$ and $q.$ We end up getting $$p + q \equiv -1 \pmod{b}$$and $$p + q \equiv -1 \pmod{2^{a+1}}.$$Since $p + q \le b \cdot 2^{a+1} \cdot 2 - 2,$ we are forced to have $$p + q = b \cdot 2^{a+1} - 1.$$Say by Pigeonhole, this implies that at least one of $p,q$ is less than or equal to $b \cdot 2^a = m,$ so plugging in that value for $T_m$ will show that all non-powers of two work. Now we will show that all $m$ of the form $2^k$ where $k \ge 1$ do not work. (Note: the above argument does not work for powers of $2$ since $b = 1$ in that case, and it is illogical to take things modulo $1.$) Once again, we require $2^{k+1} | T_m (T_m + 1).$ At least one of $T_m$ and $T_{m} +1$ is odd, so that forces all of the powers of $2$ to go into one term. But that would mean that $$T_m \ge 2^{k+1} = 2m$$if $T_m$ is even and $T_m \ge 2^{k+1} - 1 = 2m - 1$ if $T_m$ is odd. Since $k \ge 1,$ both yield clear contradictions. Therefore, the only such $m$ that work are those that are not of the form $2^k,$ where $k > 1,$ as claimed at the beginning.

We claim that the answer is everything that is either not a power of 2 or equal to 1. Let $m=2^a\cdot b$ where $a\geq 0$ and $b\geq 1$ are integers such that $b$ is odd. The condition is equivalent to the existence of $s\leq 2^a\cdot b$ such that $$s(s+1)\equiv 0\pmod{2^{a+1}\cdot b}.$$By Chinese Remainder Theorem, we can split this into $$s(s+1)\equiv 0\pmod {2^{a+1}}$$$$s(s+1)\equiv 0\pmod b.$$If $b=1$ (e.g. $m$ is a power of 2), then this is clearly not possible, as in the first congruence, $s$ and $s+1$ are opposite parity, so all $a+1$ factors of 2 must come from one of them, which is clearly not possible unless $a=0$ as $s$ is restricted to at most $2^a.$ From now on, assume $b\geq 3$. Call a number $s$ orz if $$s\equiv 0\pmod {2^{a+1}}, s\equiv -1\pmod{b}.$$Call a number $s$ xor if $$s\equiv -1\pmod {2^{a+1}}, s\equiv 0\pmod{b}.$$Note that, modulo $2^{a+1}\cdot b$, there is exactly one orz number, which we call $A$, and one xor number, which we call $B$. Note that $$A\equiv -B-1\pmod{2^{a+1}\cdot b},$$which rearranges to $$A+B\equiv -1\pmod{2^{a+1}\cdot b}.$$Obviously, $2^{a+2}\cdot b-1$ is too high as even if $A$ and $B$ are the largest possible, it is still one away. Thus, we must have $$A+B=2^{a+1}\cdot b-1.$$Thus, by Pidgeonhole, one of $A$ and $B$ is at most $2^a\cdot b-1$. Furthermore, clearly $A$ and $B$ are both nonzero, and both $s=A$ and $s=B$ satisfy $s(s+1)\equiv 0\pmod{2^{a+1}\cdot b},$ hence all non-powers of 2 work as there is some solution at most $m-1$ and we are done. (Amusingly, the part where $b\geq3$ is used is when stating that $A\neq 0$).

We claim all positive integers which are not powers of 2 greater than 1 hold. Clearly, $m=1$ satisfies the condition. We split the rest of the problem into two cases. Claim: If $m = 2^k$ for a positive integer $k \ge 1$, then $T_m = 2^{k+1} - 1 > 2^k$. We need $(T_m-1)T_m \equiv 2^{k+1}$. Since $T_m$ and $T_m - 1$ are relatively prime, the least possible value of $T_m$ is $2^{k+1} - 1$, which is greater than $2^k$ for $k \ge 1$. ${\color{blue} \blacksquare}$ Claim: If $m = 2^k \cdot n$ for an odd integer $n \ge 3$, then $T_m < m$. By CRT, there exist two distant values between $1$ and $m \cdot 2^{k+1}$ such that \begin{align*} T_{m_1} &\equiv 0~(\text{mod } n), -1~(\text{mod } 2^{k+1}) \\ T_{m_2} &\equiv -1~(\text{mod } n), 0~(\text{mod } 2^{k+1}). \\ \end{align*} Note that \[T_{m_1} \equiv 1 - T_{m_2} \implies T_{m_1}~+~T_{m_2} = 2^{k+1} \cdot n - 1 \implies \min(T_{m_1}, T_{m_2}) < 2^k \cdot n - 1 < m,\] so there exists $T_m$ such that $T_m < m$. ${\color{blue} \blacksquare}$ Thus we know $\boxed{m \text{ can be any positive integer not a power of 2 greater than 1}}$. $\blacksquare$

A very nice problem. Here is my solution. We claim that $m \ge T_m$ if and only if $m$ cannot be expressed in the form $2^k$ for some positive integer $k$. Part I: $m = 2^k$ for positive integers $k$ work. We begin by showing that if $m = 2^k$, then $m < T_m$. Observe that $S = \sum_{i = 1}^{T_n} i = \frac{T_n(T_n + 1)}{2}$, with $T_n$ and $T_n + 1$ having opposite parities. Hence, $m~|~S$ if and only if $T_n$ or $T_n + 1$ are divisible by $2^{k + 1}$. Thus $T_m = 2^{k + 1} - 1 > 2^k$. Part II: Integers $m$ that cannot be expressed as $2^k$ where $k$ is a positive integer do not work. If $\nu_2(m) = 0$, observe that $m~|~\frac{m(m - 1)}{2}$ and $m > m - 1 \ge T_m$. So it is left to consider the case when $m = 2^t \cdot K$ where $2$ does not divide $K$ and $t$ is a positive integer. Then consider the unique integers by Chinese Remainder Theorem $0 \le A, B \le 2^{t + 1} \cdot K$ such that $$A \equiv 0 \pmod{2^{t + 1}}, -1 \pmod{K}$$$$B \equiv -1 \pmod{2^{t + 1}}, 0 \pmod{K}$$ Then Chinese Remainder Theorem again gives us $A + B \equiv -1 \pmod{2^{t + 1}}$ and $A + B \equiv -1 \pmod{K}$ so $A + B = 2^{t + 1} K - 1$. Now $x = A, B$ both satisfy $n ~ | ~ \frac{x(x + 1)}{2}$ but we can simply choose $\min(A, B) \le m$ and we are done.

Notice that $m|\frac{m(m-1)}{2}$ for all odd $m$. Otherwise, let $m=2^nk$ for some odd $k$. Let odd $b\equiv k^{-1}\pmod{2^{n+1}}$. Then, let $c= bk \equiv 1\pmod{2^{n+1}}$. If $b>2^n$, then let $c= (2^{n+1}-b)k\equiv -1\pmod{2^{n+1}}$. Then, $(2^nk)|\frac{c(c-1)}{2}$ or $(2^nk)|\frac{c(c+1)}{2}$. Notice that if $k=1$, then $c=1\equiv 1\pmod{2^{n+1}}$, but $\frac{0\cdot 1}{2}$ is not a possible sum. Otherwise, $c>1$. Therefore, all integers that aren't $2^z$ for some integer $z>0$ work.

The answer is $\boxed{\text{all numbers that cannot be written in the form } 2^z, \ z>0}$ First, note that all odd numbers $k$ work since $T_k=k-1$. Now, let $k= a \cdot 2^b$. We would like to have \[a \cdot 2^{b+1} \mid T_k (T_k+1).\] Notice for $a>1$, we can let $0 \le p < a \cdot 2^{b+1}$ be a value such that \[p \equiv 0 \pmod{a}\]\[p \equiv -1 \pmod{2^{b+1}}.\] This value clearly exists by the Chinese Remainder Theorem, and setting $T_k=p$ works. However, we do not necessarily know that $k \ge p$. Also, we can let $0 \le q < a \cdot 2^{b+1}$ be a value such that: \[q \equiv -1 \pmod{a}\]\[q \equiv 0 \pmod{2^{b+1}}.\] This value exists by CRT, and setting $T_k=q$ works. We still do not know that $k \ge q$, but we have \[p+q \equiv -1 \pmod{a \cdot 2^{b+1}} \quad \text{and} \quad p+q < 2(a \cdot 2^{b+1})-1\]\[\implies p+q = a \cdot 2^{b+1}-1.\] Pigeonhole states that at least one of $p,q \le k$. It now suffices to prove that $k=2^x$ does not work. We must have \[2^{x+1} \mid T_k(T_k+1).\] Since $T_k$ and $T_k+1$ are relatively prime, the minimum value is clearly $2^{k+1}-1>2^k$.

All numbers that aren't perfect powers of $2$ with the exception of $2^0 = 1$ work. For $m = 2^k$, then $T_m = 2^{k+1} - 1$, so $m \le T_m$. For $m = n \cdot 2^k$ where $n$ is odd and greater than $3$, we will prove that $T_m \leq m$. If $k = 0$, then the maximum value of $T_m$ is $m - 1$, so it works. For $k > 0$, there are two possible values $T_{m_1}$ and $T_{m_2}$ that (could) work. By CRT, there are values that satisfy \[T_{m_1} \equiv 0\pmod{n}\]\[T_{m_1} \equiv -1\pmod{2^{k+1}}\] \[T_{m_2} \equiv -1\pmod{n}\]\[T_{m_2} \equiv 0\pmod{2^{k+1}}\] For $0 < T_{m_1}, T_{m_2} < n \cdot 2^{k+1}$. Since both of these values add up to \[T_{m_1} + T_{m_2} \equiv -1\pmod{n}\]\[T_{m_1} + T_{m_2} \equiv -1\pmod{2^{k+1}}\]\[T_{m_1} + T_{m_2} \equiv -1\pmod{n \cdot 2^{k+1}}\] So, clearly at least one of $T_{m_1} + T_{m_2}$ is $\leq n \cdot 2^k = m$, so this satisfies our conditions. Hence, all numbers that aren't perfect powers of $2$ work. (Except for $1$, of course.)

Solved with a metric ton of hints We claim that the answer is every $m$ such that $m$ is not a power of $2$ greater than $1$. It is clear that for all $m$ such that $m=2^k$, $T_m=2^{k+1}-1$ is the smallest possible solution, and this is greater than $m$ for all values of $k \ge 1$. Now assume that $m$ is not a power of $2$ greater than $1$. We see that in \[x(x+1) \equiv 0 \pmod{2m},\]$T_m$ is the smallest possible value of $x$. Let a solution $T_m$ be $\emph{nontrivial}$ if \[T_m \not\equiv 0 \pmod{2m}\]\[T_m \not\equiv 2m-1 \pmod{2m}.\]Note that if $r$ is a solution, then $(2m-1)-r$ is also a solution. Therefore, if there exists a nontrivial solution, then the condition must be satisfied because $T_m \le \tfrac{2m-1}2=m-\tfrac12$. Then it suffices to show that the number of solutions $x$ to the above congruence is greater than $2$ (or that there exists at least one nontrivial solution). Because $m$ is not a power of $2$, we write $m=2^a \cdot b$, where $b$ is odd. We have \[x(x+1) \equiv 0 \pmod{2^{a+1} \cdot b}.\]By the Chinese Remainder Theorem, we see that the systems \[x_1 \equiv 0 \pmod{2^{a+1}}\]\[x_1 \equiv -1 \pmod{b}\]and \[x_2 \equiv -1 \pmod{2^{a+1}}\]\[x_2 \equiv 0 \pmod{b}\]produce valid solutions (because $b$ is odd, we can conclude that $2^{a+1}$ and $b$ are relatively prime). In fact, we have \[x_1 \equiv -1-x_2 \pmod{2^{a+1}}\]\[x_1 \equiv -1-x_2 \pmod{b}\]\[\implies x_1 \equiv -1-x_2 \equiv (2m-1)-x_2 \pmod{2m}.\]Therefore there exists at least one nontrivial solution for all such $m$, as desired.

We claim that all $m$ not an even integral power of $2$ work. Proof they work: If $m$ is odd, we can just let $T_{m}=m$. If $m$ is even (and not a power of $2$), let $2^{k}$ be the largest power of $2$ dividing $m$ so that $m=2^{k} \cdot n$. Consider the $2^{k}$ values all less than $m$: $$\{n-1, n+1, 3n-1, 3n+1, \dots, (2^{k}-1)n-1, (2^{k}+1)n +1\}$$Note that since $n$ is odd, these numbers are the complete even residue set modulo $2^{k+1}$. If we take the value call it $a$ in the set such that $2^{k+1}$ divides it, we obtain a value $a$ less than $m$ such that $m \mid 1+ 2 +\dots+a$ concluding this part of the proof. Proof even power's of $2$ don't work : Let $m=2^{k}$ $$\frac{T_{m}(T_{m}+1)}{2} \equiv 0 \pmod{2^{k}}$$$$T_{m}(T_{m}+1) \equiv 0 \pmod{2^{k+1}}$$$$T_{m}=2^{k+1}-1$$Which is greater than $2^{k}$, for $k \geq 1$ and we are finished $\square$

We want to show that $m\geq T_m$ for any positive integer $n$ except for powers of $2$ and we ll prove that by CRT. We can easily exclude the case of $m=2^k$ by observing $n\leq 2^{k+1}-1 \Rightarrow v_2(T_n) \leq k-1$. Now if $m$ isn't a power of $2$. Since $T_n = \frac{n(n+1)}{2}$ it suffices to find an positive integer $n$ for which: \begin{align} n &\equiv 0 \pmod{2^{v_2(m)+1}} \\ n &\equiv -1 \pmod{\frac{m}{2^{v_2(m)}}} \end{align} And since the two numbers are coprime, then such an $n\leq 2m$ exist by CRT. If $n\leq m$ we're done, otherwise oen can see that if $n$ is a solution to the system, so is $2m-n$ and this latter is strictly smaller than $m$. $$\mathbb{Q.E.D.}$$

Wow, what a cool problem. I believe my solution is different to others posted above. I claim that the answer is all positive integers other than powers of $2$ greater than $1$. Let $m=2^n \cdot x$ where $v_2(m) = n$. Then, $T_n$ is the least positive integer such that $$\frac{T_n(T_n+1)}{2^{n+1} \cdot x} \in \text{Z}^{+}$$If $n=0$, then we can set $T_n = m-1$ and the conclusion is true. For the remainder of this proof we will assume $n \geq 1$. Clearly, if $x=1$ (in other words $m$ is a power of $2$), then the conclusion is false. This is true because either one of $T_n$ or $T_n+1$ cannot have a factor of $2^{n+1}$ without exceeding $m=2^n$. Note that only one of $T_n$ or $T_n+1$ can have the factors of $2$ in the denominator, and one must hold them all. Case 1: $T_n$ is the multiple of $2^{n+1}$. Then, we can write $T_n = 2^{n+1} \cdot k$ and then $2^{n+1} \cdot k \leq 2^n \cdot x \Rightarrow k \leq \frac{x}{2}$. Therefore, there is $\frac{x-1}{2}$ possible values of $T_n$ in this scenario. Case 2: $T_n+1$ is the multiple of $2^{n+1}$. Then by similar reasoning we have that $k \leq \frac{x}{2} + \frac{1}{2^{n+1}}$. Thus, $k$ has $\frac{x-1}{2}$ possible solutions in this case as well, using the fact that $n \geq 1$. Therefore, we have $x-1$ total possible values of the numerator such that the powers of $2$ cancel out. Clearly, all of the "other" factors (the one without the powers of $2$) have distinct modular residues $\pmod{x}$ (this is simply because $x$ is odd). Claim: The other factor cannot be equal to $1 \pmod{x}$. Proof: FTSOC, $k \cdot 2^n + 1 \equiv 1 \pmod{x} \Rightarrow k \equiv 0 \pmod{x}$ which contradicts the bounds on $k$ as said before. The other case follows similarly. $\square$. Thus, we have $x-1$ distinct modular residues $\pmod{x}$ which cannot be equal to $1 \pmod{x}$. Therefore there must be one equal to $0$, and the result is an integer. We are done. $\square$.

The answer is all $n$ not a perfect power of $2$ (except $1$). For all odd $n$ we see that taking $T_n = n$ works so obviously $T_n\le n$. To see that powers of $2$ fail, note that we want $2^k \mid \frac{T_n(T_n+1)}{2}$. Thus, we need $2^{k+1}\mid T_n(T_n+1)$. Since $\gcd(T_n, T_n+1) = 1$, we either have $2^{k+1}\mid T_n$ or $2^{k+1}\mid (T_n+1)$. Both of these imply $T_n > 2^k = n$, so we're done. Now, let $n = 2^k\cdot m$, where $m\ge 3$ is odd. We want $\frac{T_n(T_n+1)}{2}\equiv 0\pmod {2^k\cdot m}\implies T_n(T_n+1)\equiv 0\pmod {2^{k+1}\cdot m}.$ The key is to notice that if there exists a solution $T_n$ to this congruence, then $2^{k+1}\cdot m - T_n - 1$ is also a solution. Therefore, if there exists a solution $T_n\not\equiv 0, -1\pmod {2^{k+1}\cdot m}$, we would be done (either take $T_n$ or take $2^{k+1}\cdot m - T_n - 1$). Fortunately, this is easy to see. Since $\gcd(m, 2^{k+1})=1$, simply take $T_n \equiv 0\pmod {2^{k+1}}$ and $T_n\equiv -1\pmod m$. There exists an $x$ (by CRT) such that $T_n\equiv x\pmod {2^{k+1}\cdot m}$. We know that $x\ne 0, -1$, so we're done! $\blacksquare$ (Clearly $x(x+1)\equiv 0\pmod {2^{k+1}\cdot m}$).

We clam that all positive $m \ne 2^a$ for a positive integer $a$ works. Since $$1+2+\dots+T_n=T_n(T_n+1)/2,$$we know $T_n (T_n+1) \equiv 0 \pmod{2n}.$ Since $(2n-T_n)(T_n+1) \equiv 0 \pmod{2n}$, we know $T_n'=2n-1-T_n$ also satisfies our equation. By CRT, if $ab=2n$ where $a$ and $b$ are relatively prime, there is a solution to $$T_n \equiv 0 \pmod{a},$$$$T_n+1 \equiv 0 \pmod{b},$$with $T_n \in \{0,1,\dots,ab-1\}=\{0,1,\dots,2n-1\}.$ Note that there are solutions $T_n \ne 0,2n-1$ (this is because $T_n=0$ when $a=2n, b=1$ and $T_n=2n-1$ when $a=1, b=2n$, and there exists $a,b \ne 1$ when $m$ is not a power of $2$). If this $0<T_n \le n,$ we are done. If $2n-1>T_n>n,$ we know $0<2n-1-T_n < n-1$ is also a solution, and we are done. \qed