Para cada entero positivo $n$, se define $T_n$ como el menor entero positivo tal que $1+2+\cdots +T_n$ es múltiplo de $n$. Por ejemplo, $T_5=4$ puesto que $1$, $1+2$ y $1+2+3$ no son múltiplos de $5$, pero $1+2+3+4$ sí es múltiplo de $5$.
Determine todos los enteros positivos $m$ tales que $T_m\geq m$.
Nota. Todo entero positivo es múltiplo de sí mismo.
Si $n>1$ es impar, es $T_n \leq n-1$ ya que
$1+2+ \ldots + n-1 = \frac{n(n-1)}{2} \equiv 0 \pmod{n}$
¿Qué pasará en el caso opuesto?
Si $n = 2^k$ entonces para todo $m < n = 2^k$ es
$1 +2 +\ldots + m = \frac{m(m+1)}{2}$ el cual es imposible que sea múltiplo de $2^k = n$
Si $n = 2^kI$ con $I > 1$ impar, entonces $gcd(I,2) = 1$
En este caso como $gcd(I,2^k) = 1$, buscamos $j<2^k$ tal que $Ij \equiv \pm 1 \pmod{2^{k+1}}$ y verifique alguna de las siguientes
$1+ 2+ \ldots + jI \equiv \frac{(jI)(jI+1)}{2}$
$1+ 2 + \ldots + jI -1 \equiv \frac{(jI)(jI-1)}{2}$
La pregunta es, existe tal $j$ ?
En particular, sabemos que dentro del rango $0 < j < 2^{k+1}$ este $j$ es único.
Supongamos entonces que las soluciones que encontramos a $xI \equiv 1 \pmod{2^{k+1}}$ e $yI \equiv -1 \pmod{2^{k+1}}$ son ambas mayores (estricto) que $2^{k}$.
Como $x \neq y$ y son impares, podemos suponer que $2^k < x < y < 2^{k+1}$, luego $z = \frac{y-x}{2} \in \mathbb{N}$ verifica
$zI \equiv \frac{1}{2} (-1- 1) \equiv \frac{2}{2} \pmod{2^{k+1}}$.
Luego $zI \equiv -1 \pmod{2^{k+1}}$ con $0 < z < 2^{k}$
Primero que nada, vemos que la suma pedida es $\frac{T_n(T_n+1)}{2}$, en realidad los $T_n$ casi nunca van a aparecer, lo que importa es que la cuenta nos da un número de la forma $\frac{k(k+1)}{2}$. De acá sale la observación clave del problema: Como $k$ y $k+1$ son coprimos, si queremos que la fracción sea múltiplo de $n$, entonces los factores primos de $n$ van a estar "separados" entre $k$ y $k+1$ (o sea, si por ejemplo $k$ es múltiplo de $3$, todos los factores $3$ de $n$ tienen que estar en $k$).
Vamos a resolver primero el caso donde $T_n<n$, para el que nos alcanza simplemente con fabricar un número $x<n$ tal que $\frac{x(x+1)}{2}$ sea múltiplo de $n$. Este es el caso en que $n$ no es una potencia de $2$.
Como no es potencia de $2$, tenemos que $n=2^k\cdot (2t+1)$ con $t$ entero positivo. Por lo que dijimos antes, cada primo que divide a $n$ va a aparecer en uno sólo entre $x$ y $x+1$, como el único primo del que tenemos información es $2$, vamos a tratar de hacer que uno de los números sea múltiplo de $2t+1$ y el otro tenga todos los factores $2$, pero como estamos dividiendo por $2$, en realidad lo que necesitamos es que sea múltiplo de $2^{k+1}$.
Notemos entonces que como $2t+1$ y $2^{k+1}$ son coprimos, $2t+1$ tiene inverso módulo $2^{k+1}$, es decir, existe $0<m<2^{k+1}$ tal que $(2t+1)m\equiv 1\pmod{2^{k+1}}$.
Si $m<2^k$, entonces eligiendo $x=(2t+1)m-1$ tenemos que $x$ es múltiplo de $2^{k+1}$ y $x+1=(2t+1)m$ es múltiplo de $2t+1$, como $x<n$ ya tenemos el ejemplo.
Ahora, si $m>2^k$ (no puede ser $2^k$ porque no es invertible), entonces $2^{k+1}-m<2^k$, además $\left (2^{k+1}-m\right )(2t+1)\equiv -m(2t+1)\equiv -1\pmod{2^{k+1}}$, entonces eligiendo $x=\left (2^{k+1}-m\right )(2t+1)$ tenemos que $x$ es múltiplo de $2t+1$ y $x+1$ es múltiplo de $2^{k+1}$, como $x<n$ ya tenemos el ejemplo.
Ahora, cuando $n$ es una potencia de $2$ esta construcción no anda, básicamente porque $2t+1=1$ y entonces $m=1$, así que no hay mucho que podamos hacer.
Para demostrar que si $n=2^k$ entonces $T_n\geq n$, recurrimos nuevamente a la observación clave, todos los factores $2$ van a tener que estar en $x$ o en $x+1$, más aún, al que le toque va a tener que ser múltiplo de $2^{k+1}$ para cubrir al $2$ que está dividiendo. Si $x$ es múltiplo de $2^{k+1}$ entonces claramente es mayor que $n$. Si $x+1$ es múltiplo de $2^{k+1}$ entonces $x+1\geq 2n$, si pasara que $x<n$ tendríamos $2n\leq x+1<n+1$, de modo que $n<1$, absurdo. Entonces $x\geq n$.
En ambos casos si un número cumple lo pedido tiene que ser mayor o igual a $n$, de modo que $T_n\geq n$, y con eso estamos.
En resumen, los números que cumplen lo que dice el enunciado son las potencias de $2$.
