Asumimos que existe $n$ tal que $n | 2^{n} + 1.$
Notemos que por teorema de Zsigmondy $\forall n \geq 1$ $\exists$ $p \in primos$ $/$ $p$ divide a $a^n - b^n$ y $p$ no divide a $a^k - b^k$ $/$ $k<n$ y $k$ $;n \in Z^+$ con $a = 2$ coprimo con $b = 1$ y $n = 2n$
Tomo $p$ tal que $p | 2^{2n} - 1^{2n}$
Sea $p \neq 2 \Rightarrow $$2^{2n} \equiv 1 (mod$ $p) \Rightarrow $ tomo $ k = n < 2n \Rightarrow p$ no divide a $ 2^n-1 \Rightarrow $ como $ p | 2^{2n} - 1$$ \Rightarrow p | (2^n-1)(2^n+1) $ y como $p$ no divide a $ 2^n-1$ y es primo$ ; $ concluimos que $ p | 2^n + 1$
Notemos que el teorema sirve para todo $n$, por lo que podemos tomar $n = p_i$ con $p_i$ primo. Sabemos que $a^n \equiv b^n (mod$ $p_i)$ y por Fermatito $a \equiv b (mod$ $p_i)$ y con $a = 2$ y $b = 1$ es un absurdo que vino por asumir que $n = p$. Concluimos que $n$ coprimo con $p$.
Sabiendo que $n$ y $p$ son coprimos y que ambos dividen a $2^n + 1$, por divisibilidad $\Rightarrow$ $np | 2^n + 1$ $\Rightarrow$ elevamos a la $p$ ambos miembros y como es impar resulta que $2^{np}\equiv -1^p (mod$ $np)$ y por ende $ np | 2^{np} + 1$
Llamo $\psi \in Z^+$ al número generado por aplicar la propiedad con 2000 primos distintos para un $n$ tal que $n\geq 3 \land n|2^{n}+1$ y para un $p$ tal que $p \neq 2$ $\land$ $np|2^{np} + 1$, repitiendo el procedimiento del enunciado. Esta vez nuestro $n$ del teorema de Zsigmondy será $2np$ y nuestro nuevo $p$ será $p_2$.
Notemos que $\psi$ tiene exactamente 2000 divisores primos distintos y $\psi | 2^\psi+1$. $\Box$
Última edición por Nicolas Valen el Mar 18 Ago, 2020 5:34 pm, editado 1 vez en total.
Asumimos que existe $n$ tal que $n | 2^{n} + 1.$
Notemos que por teorema de Zsigmondy $\forall n \geq 1$ $\exists$ $p \in primos$ $/$ $p$ divide a $a^n - b^n$ y $p$ no divide a $a^k - b^k$ $/$ $k<n$ y $k$ $;n \in Z^+$ con $a = 2$ coprimo con $b = 1$ y $n = 2n$
Tomo $p$ tal que $p | 2^{2n} - 1^{2n}$
Sea $p \neq 2 \Rightarrow $$2^{2n} \equiv 1 (mod$ $p) \Rightarrow $ tomo $ k = n < 2n \Rightarrow p$ no divide a $ 2^n-1 \Rightarrow $ como $ p | 2^{2n} - 1$$ \Rightarrow p | (2^n-1)(2^n+1) $ y como $p$ no divide a $ 2^n-1$ y es primo$ ; $ concluimos que $ p | 2^n + 1$
Notemos que el teorema sirve para todo $n$, por lo que podemos tomar $n = p_i$ con $p_i$ primo. Sabemos que $a^n \equiv b^n (mod$ $p_i)$ y por Fermatito $a \equiv b (mod$ $p_i)$ y con $a = 2$ y $b = 1$ es un absurdo que vino por asumir que $n = p$. Concluimos que $n$ coprimo con $p$.
Sabiendo que $n$ y $p$ son coprimos y que ambos dividen a $2^n + 1$, por divisibilidad $\Rightarrow$ $np | 2^n + 1$ $\Rightarrow$ elevamos a la $p$ ambos miembros y como es impar resulta que $2^{np}\equiv -1^p (mod$ $np)$ y por ende $ np | 2^{np} + 1$
Llamo $\psi \in Z^+$ al número generado por aplicar la propiedad con 2000 primos distintos para un $n$ tal que $n\geq 3 \land n|2^{n}+1$ y para un $p$ tal que $p \neq 2$ $\land$ $np|2^{np} + 1$, repitiendo el procedimiento del enunciado. Esta vez nuestro $n$ del teorema de Zsigmondy será $2np$ y nuestro nuevo $p$ será $p_2$.
Notemos que $\psi$ tiene exactamente 2000 divisores primos distintos y $\psi | 2^\psi+1$. $\Box$
La construcción que hiciste está bien, pero no demostraste que si $n\mid 2^n+1$, entonces $2^n+1$ tiene un factor primo $p$ que no divide a $n$.
Con Fermatito vos demostraste que si $p$ es primo, entonces $p$ no divide a $2^p-1$, pero eso no alcanza todavía.
Armamos la sucesión $a_n$ de la siguiente manera, $a_1=3$ y $a_{n+1}$ es igual a $a_np$ si es que existe un primo $p$ que divide a $2^{a_n}+1$ y no a $a_n$, si no existe tal $p$, $a_{n+1}=2^{a_n}+1$.
Veamos inductivamente que $a_n$ divide a $2^{a_n}+1$ para todo $n$, supongamos que pasa para $n$ y $a_nk=2^{a_n}+1$.
Si $a_{n+1}=a_{n}p$ entonces, como $2^{a_n}≡-1$ modulo $a_n$ y $p$ es impar (divide a $2^{a_n}+1$), $2^{a_np}≡-1$ modulo $a_n$ y como $2^{a_n}≡-1$ modulo $p$ también, $2^{a_np}≡-1$ modulo $p$, por lo tanto como $a_n$ y $p$ son comprimos, $2^{a_np}≡-1$ modulo $a_np$ que implica, $a_{n+1}$ divide a $2^{a_{n+1}}+1$
Si $a_{n+1}=2^{a_n}+1$, entonces $2^{a_n}≡-1$ modulo $2^{a_n}+1$, elevando ambos miembros a la $k$ (es impar), $2^{a_nk}=2^{2^{a_n}+1}≡-1$ modulo $2^{a_n}+1$ por tanto $a_{n+1}$ divide a $2^{a_{n+1}}+1$. En el caso base $n=1$ se cumple, ya que $3$ divide a $9$.
Lema: para todo $m>3$, $2^m+1$ tiene un factor primo $p$ que no tiene ningún $2^j+1$ para todo $j<m$
Demostración: Por el teorema de Bang, para todo $m>3$, $2^{2m}-1$ tiene un factor primo $p$ que no tiene ningún $2^{x}-1$ con $x<2m$, luego como $2^{2m}-1=(2^m-1)(2^m+1)$, y por lo anterior, entonces $p$ divide a $2^m+1$, por ultimo si $p$ divide a $2^j+1$ con $j<m$ entonces $p$ divide a $2^{2j}-1$ lo cual es absurdo ya que $2j<2m$.
Ahora vemos que $a_{n+1}$ tiene un primo más en su factorización que $a_n$ si $a_{n+1}=a_{n}p$ o exactamente los mismos si $a_{n+1}=2^{a_n}+1$.
Miremos también que si $a_{n+1}=2^{a_n}+1$, entonces $a_{n+2}=(2^{a_n}+1)p$ ya que por el lema $2^{2^{a_n}+1}+1$ tiene un factor primo $p$ que no tiene $2^{a_n}+1$. Finalmente vemos que en la secesión la cantidad de factores primos de los términos va aumentando eventualmente de a uno, pasando por todos los naturales y en particular por $2000$ y por lo demostrado en la inducción, existe el número pedido en el problema.
Vamos a probar el resultado por inducción en $k$, donde $k$ es la cantidad de factores primos de $n$.
El caso base $k=1$ es cierto, tomando por ejemplo $n=3$.
Supongamos como hipótesis inductiva que vale para $k$. Veamos que vale para $k+1$.
En efecto, tenemos que existe un $n$ con exactamente $k$ factores primos distintos tal que $n\mid 2^n+1$. Entonces si encontramos un $p$ tal que $np\mid 2^{np}+1$ y $p\not \mid n$, resulta que $n'=np$ tiene exactamente $k+1$ factores primos distintos y $n'\mid 2^{n'}+1$.
Ahora, notemos que $2^n+1\mid 2^{np}+1$, que es el caso particular cuando $a=2^n$ y $b=1$ de $a+b\mid a^{2m+1}+b^{2m+1}$, esto puede verse usando la identidad\begin{align*}a^{2m+1}+b^{2m+1} & =(a+b)\sum \limits _{j=0}^{2m}(-1)^ja^jb^{2m-j} \\
& =(a+b)\left (a^{m-1}-a^{m-2}b+\ldots -ab^{m-2}+b^{m-1}\right ),
\end{align*}que sale simplemente distribuyendo y viendo que se cancela todo, o bien notando que $a\equiv -b\pmod{a+b}$, por lo que $a^{2m+1}\equiv (-b)^{2m+1}\equiv -b^{2m+1}\pmod{a+b}$, de modo que $a^{2m+1}+b^{2m+1}\equiv 0\pmod{a+b}$. Por lo tanto, basta tomar un primo $p$ tal que $p\mid 2^n+1$ y $p\not \mid n$ (notar que la identidad funciona porque $p$ es impar).
Notemos también que $n\mid 2^{\varphi (n)}-1$ por Fermat-Euler, entonces basta encontrar un primo $p$ tal que $p\mid 2^n+1$ y $p\not \mid 2^{\varphi (n)}-1$ (esto nos garantiza que no divide a $n$, ya que en caso contrario dividiría a $2^{\varphi (n)}-1$).
Bueno, ahora, por Zsigmondy, $2^{2n}-1=\left (2^n-1\right )\left (2^n+1\right )$ tiene un divisor primo $p$ que no divide a $2^t-1$ para $t<2n$, en particular, no divide a $2^n-1$ ni a $2^{\varphi (n)}-1$, pues $\varphi (n)<n<2n$, entonces al ser primo debe dividir a $2^n+1$. Este primo $p$ cumple lo que queríamos. La inducción está completa.
En particular, el resultado vale para $k=2000$, y con eso estamos.
