Como en el título. Es muy fácil demostrar que $5|2^{122}+1$, pero ¿qué debo hacer para demostrar que $\frac{2^{122}+1}{5}$ es un número compuesto? Estoy buscando pistas.
Respuestas
¿Demasiados anuncios?
Matt Dawdy
Puntos
5479
Supongamos que un primer $p$ divide $2^{122} + 1$. Esto significa exactamente eso $2^{122} \equiv -1 \bmod p$. En particular, $2^{244} \equiv 1 \bmod p$ pero $2^{122} \not \equiv 1 \bmod p$, lo que significa (si $p \neq 2$, lo que está claro) que $2$ ha pedido dividiendo $244$ pero no dividiendo $122$ en el grupo multiplicativo $\mathbb{F}_p^{\times}$. Los pedidos con esta propiedad se $244$$4$. En el último caso,
$$2^{122} \equiv 2^2 \equiv 4 \equiv -1 \bmod p$$
implica que $p = 5$. En el primer caso, desde la $\mathbb{F}_p^{\times}$ orden $p - 1$, se deduce que el $244$ debe dividir $p - 1$; equivalentemente,
$$p \equiv 1 \bmod 244.$$
Así que cuando usted busca para la división de los números primos $2^{122} + 1$ otros de $5$, puede restringir su atención a los números primos congruentes a $1 \bmod 244$. La secuencia de enteros positivos congruente a $1 \bmod 244$ comienza
$$1, 245, 489, 733, \dots$$
y de estos a $5 \mid 245, 3 \mid 489$, e $733$ es primo (por la prueba de la división). A partir de aquí solo necesita computar $2^{122} \bmod 733$, por ejemplo, el uso de exponenciación binaria. Esto no es tan malo, especialmente si se escribe como $2^{2^7 - 4 - 2}$.
Este es un caso especial de una más general sobre los cyclotomic polinomios $\Phi_n(x)$, que es que todos los números primos dividiendo $\Phi_n(a)$ son congruentes a $1 \bmod n$. Aquí $n = 244$$\Phi_{244}(2) = \frac{2^{122} + 1}{5}$. Esta observación puede ser usado para demostrar que hay infinitamente muchos de esos primos sin el uso del teorema de Dirichlet.
$$1+2^{122}=\left(1+2^{61}\right)^2-\left(2^{31}\right)^2$$
$$=\left(1+2^{61}+2^{31}\right)\left(1+2^{61}-2^{31}\right)$$
Ambos factores son mayores que los de $5$, también se $$2^{122}\equiv \left(2^4\right)^{30}\cdot 2^2\equiv (1)^{30}\cdot 2^2\equiv -1\pmod{5},$$, de modo que el resultado de la siguiente manera.
De manera más general, la siguiente se llama Sophie Germain de identidad (para todos los $a,b\in\mathbb R$):
$$a^4+4b^4=\left(a^2+2b^2\right)^2-\left(2ab\right)^2$$
$$=\left(a^2+2b^2+2ab\right)\left(a^2+2b^2-2ab\right)$$
La siguiente factorización es un Aurifeuillean de la factorización de (para todos los $k\in\mathbb R$):
$$2^{4k+2}+1=\left(2^{2k+1}-2^{k+1}+1\right)\left(2^{2k+1}+2^{k+1}+1\right)$$
Algunos otros Aurifeuillean factorizations (no relacionadas con la Sophie Germain identidad):
$$3^{6k+3}+1=\left(3^{2k+1}+1\right)\left(3^{2k+1}-3^{k+1}+1\right)\left(3^{2k+1}+3^{k+1}+1\right)$$
$$5^{10k+5}-1=\left(5^{2k+1}-1\right)\left(5^{4k+2}+5^{3k+2}+3\cdot 5^{2k+1}+5^{k+1}+1\right)\times$$
$$\times \left(5^{4k+2}-5^{3k+2}+3\cdot 5^{2k+1}-5^{k+1}+1\right)$$
$$6^{12k+6}+1=\left(6^{4k+2}+1\right)\left(6^{4k+2}+6^{3k+2}+3\cdot 6^{2k+1}+6^{k+1}+1\right)\times$$
$$\times \left(6^{4k+2}-6^{3k+2}+3\cdot 6^{2k+1}-6^{k+1}+1\right)$$
Hay muchos más de estos en la página de la Wikipedia sobre Aurifeuillean de la factorización.
Simon D
Puntos
1414
$2^{122}+1=(2^{61}+2^{32}+1)*(2^{61}-2^{32}+1)$
Esta es una factorización de gauss basado en $(2x²+2x+1)(2x²-2x+1)=4x^4+1$.
El primero de ellos es un múltiplo de a $5$.
De hecho, los factores de gauss (en cualquier base) dividir el algebraicas raíces están destinados en dos divisores, y el mismo divisores siempre aparecen en el mismo lado (aquí varios de $5$ vs no-varios de $5$). Así por ejemplo encontramos siempre $29$ $5$ factor, y $113$ frente a ella.
