4 votos

Cómo probar o refutar $n$ es primo?

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

1voto

Casteels Puntos 8790

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}$.

1voto

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$.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X