Ecuación

Question

Quiero encontrar todas las soluciones de la ecuación de $x = \tau(2^x – 1)$, entero donde $\tau(n)$ es el número de divisores de n.

Sé que 1, 2, 4, 6, 8, 16 y 32 son soluciones, pero no tengo ni idea de cómo resolver esta ecuación en general.

Cualquier ayuda será apreciada.

Answer 1

Para todos los números naturales $n$ y prime $p$, vamos a $e_p(n)$ ser el exponente de la potencia más alta de $p$ división $n$. $\omega(n)$ es la cantidad de únicos factores primos de a $n$ $\Omega(n)$ es la cantidad de factores primos de a $n$ contando multiplicidad.

Lema 1 Para todos los números naturales $n\in\mathbb{N}$ y números primos $p$ tenemos: $$\omega(2^{p^{n}}-1)\ge n$$ Prueba: vamos a probar esto por inducción. Está claro que $\omega(2^p-1)\ge 1$. Ahora, suponga que $\omega(2^{p^{n-1}}-1)\ge n-1$. Vamos a probar ahora que $\omega(2^{p^n}-1)\ge n$. Sabemos que: $$2^{p^n}-1=(2^{p^{n-1}}-1)(2^{p^{n-1}(p-1)}+2^{p^{n-1}(p-2)}+\ldots+1)$$ Por lo que es suficiente para demostrar que: $$\gcd(2^{p^{n-1}}-1,2^{p^{n-1}(p-1)}+2^{p^{n-1}(p-2)}+\ldots+2^{p^{n-1}}+1)=1$$ Sabemos que: $$2^{p^{n-1}(p-1)}+2^{p^{n-1}(p-2)}+\ldots+2^{p^{n-1}}+1\equiv p\pmod {2^{p^{n-1}}-1}$$ Así: $$\gcd(2^{p^{n-1}}-1,2^{p^{n-1}(p-1)}+2^{p^{n-1}(p-2)}+\ldots+2^{p^{n-1}}+1)=\gcd(2^{p^{n-1}}-1,p)$$ ahora, es suficiente para demostrar que $2^{p^{n-1}}\not\equiv 1\pmod p$ y que es bastante obvio (sugerencia: FLT). Ahora estamos hecho con la inducción de paso, y así lo hemos demostrado por inducción que $\omega(2^{p^n}-1)\ge n$. Q. E. D.

Lema 2 Para todos los números naturales $n\in\mathbb{N}$ tenemos: $$\omega(2^n-1)\ge\Omega(n)$$ Prueba: Escribe: Para todos el primer potencias $p^k\mid n$ tenemos $2^{p^k}-1\mid 2^n-1$. Ahora, tome dos primos $p\neq q$ y dos enteros $k$$\ell$. Deje $d=\gcd(2^{p^k}-1,2^{q^{\ell}}-1)$. Es evidente que existe cierta $r$ tal que para todo natural $m$: $$d\mid 2^m-1\Longleftrightarrow r\mid m$$ Por lo tanto,$r\mid \gcd(p^k,q^\ell)=1$, lo $d\mid 2^1-1=1$, lo $d=1$. Llegamos a la conclusión de que $2^{p^k}-1$ $2^{q^\ell}-1$ son coprime, así: $$\omega(2^n-1)\ge \sum_{p\mid n}\omega(2^{p^{e_p(n)}}-1)$$ Ahora sigue directamente del lema 1 $\omega(2^n-1)\ge\Omega(n)$. Q. E. D.

Lema 3 Para todos los números naturales $n\in\Bbb{N}$, tenemos: $$\Omega(\tau(n))\ge \omega(n)$$ Prueba: podemos escribir: $$\tau(n)=\prod_{p\text{ prime}}(e_p(n)+1)$$ La cantidad de factores en el lado derecho no es igual a $1$$\omega(n)$, pero la cantidad de factores en el lado derecho no es igual a $1$ también es menor o igual a $\Omega(\tau(n))$ y hemos terminado. Q. E. D.

---

Con estos tres lemas por fin podemos echar un vistazo a su problema. Supongamos que para algunos $n$ (yo uso $n$ en lugar de $x$) tenemos que: $$n=\tau(2^n-1)$$ Así: $$\Omega(n)=\Omega(\tau(2^n-1))$$ Por el lema $3$, se puede concluir que: $$\Omega(n)\ge \omega(2^n-1)$$ Pero lexema $2$ dice que $\omega(2^n-1)\ge \Omega(n)$, por lo que podemos concluir que: $$\Omega(n)=\omega(2^n-1)$$

---

Ahora, vamos a proceder con @barto de la prueba en los comentarios. Una prueba rápida revela que $n=6$ es la solución. Para el resto de la prueba, podemos suponer que la $n\neq 6$. Zsigmody del teorema da ahora: $$\Omega(n)=\omega(2^n-1)\ge\tau(n)-1$$ o, por escrito differentely: $$\sum_{p\text{ prime}}e_p(n)+1\ge \prod_{p\text{ prime}}(e_p(n)+1)$$ El uso de la inducción, que ahora puede ser demostrado que no sólo puede ser un primer $p$$e_p(n)\neq 0$, lo $n$ es una fuente primaria de energía, decir $n=p^k$.

Ahora tenemos: $$p^k=\tau(2^{p^k}-1)$$ Para $p$ impar, obtenemos que $2^{p^k}-1$ debe ser el cuadrado de un número impar. Para $p^k>2$ este extraño cuadrado es congruente a $-1$ modulo $8$, lo cual es imposible. Las pruebas revelan $n=1$ $n=2$ son opciones posibles. Para el resto, debemos tener $p=2$. Entonces, para todos los enteros positivos $j<k$, tenemos: $$\frac{2^{p^{j+1}}-1}{2^{p^j}-1}=2^{2^j}+1$$ prime. Sin embargo, $2^{2^5}+1$ no es primo, por lo $k\le 5$. Esto le da al candidato soluciones: $$n\in\{1,2,4,8,16,32\}$$ y como resulta que esa todo el trabajo.

Llegamos a la conclusión de que las únicas soluciones de $n=\tau(2^n-1)$ son: $$n\in\{1,2,4,6,8,16,32\}$$