Vamos a recordar un lema: Si [math]p es un primo de la forma [math]4k+3 y [math]p \mid a^2 + b^2 entonces [math]p\mid a y [math]p \mid b.
Si [math]n=1 no hay nada que demostrar. Si [math]n\geq 2 entonces [math]2^n -1 \equiv 3 \pmod{4} entonces, tiene algún divisor primo de la forma [math]4k+3. Sea [math]p un primo de esa pinta tal que [math]p\mid 2^n - 1. Luego, como [math]2^n - 1 \mid m^2 + 3^2 se sigue que [math]p\mid m^2 + 3^2. Por nuestro lema, se sigue que [math]p\mid m y [math]p\mid 3, de donde [math]p=3 y [math]3\mid m. Se ve entonces que el único divisor que puede tener de esta forma es [math]3.
Entonces, [math]2^n - 1 \equiv 0 \pmod{3}. Se sigue fácilmente que [math]n es par. Si escribimos [math]n=2^i k con [math]k impar y hacemos diferencias de cuadrados, nos queda [math]2^{2^i k} - 1 = (2^k - 1)(2^k+1)(2^{2k}+1)\cdots (2^{2^{i-1}k}+1).
Supongamos que [math]k>1, entonces [math]2^k -1 \equiv 3 \pmod{4}. Luego, tiene algún divisor primo [math]q de la forma [math]4k+3. Entonces, por lo que dijimos antes, [math]q debe ser [math]3. Pero notemos que [math]k es impar, entonces [math]2^k - 1 \equiv 1 \pmod{3}. Absurdo.
Se sigue así que [math]k=1, y si [math]n anda entonces debe ser una potencia de [math]2.
Ahora demostremos que para todo [math]n que sea potencia de [math]2 entonces existe algún [math]m tal que [math]2^{n}-1 \mid m^2 +9.
Vamos a demostrar que el único primo de la forma [math]4k+3 que aparece en estos números es [math]3.
Denotamos [math]n=2^k. Tenemos que [math]2^{2^k} - 1 = \prod_{d\mid 2^k} \Phi_d (2) por la Propiedad 1 sobre polinomios ciclotómicos y lo evaluamos en [math]X=2.
Sea [math]p un primo tal que [math]p\mid \Phi_{2^m}(2). Por el Teorema 1 tenemos que [math]p\mid 2^m \Rightarrow p=2 o [math]p \equiv 1 \pmod{2^m}, de donde si [math]m>1 tenemos que es de la forma [math]4k+1. Consideramos entonces [math]\Phi_{1}(2)\Phi_{2}(2). Por la propiedad 1, eso es igual a [math]2^2 - 1 = 3. De donde si [math]p es de la forma [math]4k+3 debe ser [math]3. Se ve de esta forma también que [math]3\parallel 2^{2^k}-1.
Ahora, sea [math]3 \cdot p_1^{\alpha_1} \cdots p_t^{\alpha_t} la factorización en primos de [math]2^{2^k}-1. Quiero que [math]2^{2^k}-1 \mid 9(m'^2+1), es decir [math]p_1^{\alpha_1} \cdots p_t^{\alpha_t} \mid m'^2 + 1 (pues es coprimo con [math]3).
Notemos que [math]-1 es residuo cuadrático módulo [math]p primo sii es de la forma [math]4k+1. Como todos los primos [math]p_1, \ldots ,p_t son de esa forma, se sigue que [math]\left( \dfrac{-1}{p_i}\right)=1 donde [math]\left( \dfrac{a}{b} \right) es el símbolo de Legendre. El símbolo de Jacobi nos dice [math]\left( \dfrac{-1}{p_1^{\alpha_1}\cdots p_t^{\alpha_t}} \right) = \left( \dfrac{-1}{p_1} \right)^{\alpha_1} \cdots \left( \dfrac{-1}{p_t} \right)^{\alpha_t} = 1.
Luego [math]-1 es residuo cuadrático módulo [math]p_1^{\alpha_1} \cdots p_t^{\alpha_t}. Por la definición, se sigue que existe un [math]m\in\mathbb{Z} tal que [math]m'^2 \equiv -1 \pmod{p_1^{\alpha_1} \cdots p_t^{\alpha_t}} y estamos. [math]\blacksquare
"Though my eyes could see I still was a blind man"
Desvirtuo un poco, pero me parece interesante el simbolo de Jacobi, lei un poco sobre que servia para algoritmos de primalidad no deterministicos cuando me puse a investigar como funcionaba el algoritmo RSA, que de hecho es un algoritmo que me parece muy simple para el uso que tiene, bello en pocas palabras :p
Dan miedo algunos de los problemas de la IMO :p
Nacho escribió: ↑Jue 31 May, 2012 3:16 pm
Vamos a recordar un lema: Si $p$ es un primo de la forma $4k+3$ y $p \mid a^2 + b^2$ entonces $p\mid a$ y $p \mid b$.
Si $n=1$ no hay nada que demostrar. Si $n\geq 2$ entonces $2^n -1 \equiv 3 \pmod{4}$ entonces, tiene algún divisor primo de la forma $4k+3$. Sea $p$ un primo de esa pinta tal que $p\mid 2^n - 1$. Luego, como $2^n - 1 \mid m^2 + 3^2$ se sigue que $p\mid m^2 + 3^2$. Por nuestro lema, se sigue que $p\mid m$ y $p\mid 3$, de donde $p=3$ y $3\mid m$. Se ve entonces que el único divisor que puede tener de esta forma es $3$.
Entonces, $2^n - 1 \equiv 0 \pmod{3}$. Se sigue fácilmente que $n$ es par. Si escribimos $n=2^i k$ con $k$ impar y hacemos diferencias de cuadrados, nos queda $2^{2^i k} - 1 = (2^k - 1)(2^k+1)(2^{2k}+1)\cdots (2^{2^{i-1}k}+1)$.
Supongamos que $k>1$, entonces $2^k -1 \equiv 3 \pmod{4}$. Luego, tiene algún divisor primo $q$ de la forma $4k+3$. Entonces, por lo que dijimos antes, $q$ debe ser $3$. Pero notemos que $k$ es impar, entonces $2^k - 1 \equiv 1 \pmod{3}$. Absurdo.
Se sigue así que $k=1$, y si $n$ anda entonces debe ser una potencia de $2$.
Ahora demostremos que para todo $n$ que sea potencia de $2$ entonces existe algún $m$ tal que $2^{n}-1 \mid m^2 +9$.
Doy una forma de terminarlo un poco diferente (aunque en el fondo es lo mismo usando menos nombres nuevos):
Vamos a usar dos lemas, el usado en la solución anterior que llamaremos Lema 1 y otro que será el Lema 2 (es el Lema 3 del post).
Recordemos que aplicando reiteradas veces diferencia de cuadrados obtenemos
Supongamos que existe un divisor primo $p$ de $2^{2i}-1$ de la forma $4k+3$ y que $p\neq 3$. Observamos que $p$ debe dividir a alguno de los factores de la pinta $(2^{2^b}+1)$ con $1 \leq b \leq i$, pero por el Lema 1 tenemos que $p \mid 1$ lo cual es absurdo. Luego el único divisor primo de la forma $4k+3$ de $2^n - 1$ es $p=3$. Notemos además que los factores de la pinta $(2^{2^b}+1)$ son impares y coprimos con $3$ ya que $2^{2^b} + 1\equiv 1 + 1 \equiv 2 \pmod 3$. Entonces $2^n-1 = 3 \cdot b$ donde $b$ es un número cuyos divisores primos son todos de la forma $4k+1$ y como consecuencia del Lema 2 tenemos que $-1$ es residuo cuadrático módulo $b$, es decir que existe un $b'$ tal que $b \mid (b')^2 + 1$. Concluímos que