Deje $n$ ser un número impar tal que
$$2^{\frac{n-1}{2}}\equiv -1 \pmod{n}$$
¿Cómo puedo probar o refutar $n$ es primo?
Este problema es de cuando he resuelto otro problema. Gracias
Respuestas
¿Demasiados anuncios?
El método básico para una rápida exponenciación es primero encontrar la base 2 de la expansión de $1638$, es decir, el aviso de que $1638=2+2^2+2^5+2^6+2^9+2^{10}$.
En el otro lado, $2^2\equiv 4 \pmod{3277}$, $2^{2^2}\equiv 16 \pmod{3277}$, $2^{2^3}\equiv 256 \pmod{3277}$ y $2^{2^4}\equiv -4 \pmod{3277}$, $2^{2^5}\equiv 16 \pmod{3277}$, $2^{2^6}\equiv 256 \pmod{3277}$, $2^{2^7}\equiv -4 \pmod{3277}$, $2^{2^8}\equiv 16 \pmod{3277}$, $2^{2^9}\equiv 256 \pmod{3277}$, $2^{2^{10}}\equiv -4 \pmod{3277}$. Tenga en cuenta que para llegar a cada término, sólo estoy cuadrando el término anterior, así que este es un muy rápido cálculo.
Por lo tanto, $2^{1638}\equiv 2^{2+2^2+2^5+2^6+2^9+2^{10}}\equiv (4)(16)(16)(256)(256)(-4)\equiv -1 \pmod{3277}$.
Simon D
Puntos
1414
Hay tres tipos de solución a este tipo de cosas - de los números primos, pseudo los números primos y los números de carmichael.
Si se soluciona algo como $3^{\frac{n-1}n} = -1 \pmod{n}$, y esta falla, a continuación, $n$ es un pseudoprime a 2, pero no de 3.
Si a solucionar esto, y obtener un resultado positivo para $3$ así, entonces usted podría estar tratando con un carmicahel-número, un producto de tres o más números primos $p_n$ donde $p_n-1$ divide el número menos uno. Un ejemplo es $601\times 1201 \times 1801$.
Hay casos como $43\times 127$, lo que ha período que divide 42 para todas las bases de $2^a 5^b$.
Si usted sabe algunos trucos, usted puede buscar alrededor para $a\text{^^}{\frac {n+1}2} = -2$, donde el ^^ operador da $p\text{^^}n= a^n+a^{-n}$, e $p\text{^^}0 = 2, p\text{^^1}=p$. Esta es la forma de cazar Messerine de los números primos, donde $p=4, n=2^x$.
