Pruebas de primalidad

Question

Tengo esta forma de probar primos mayores que 2.

Divido $2^{n-1} - 1$ por n. Si el resto es 0, n es primo.

Esto funciona porque en GF(p), si uno multiplica todos los elementos distintos de cero en el campo por el mismo número distinto de cero (digamos 2), todos los números simplemente se reordenan.

Así, si se multiplican los productos entre sí, el producto es el mismo que si no se hubiera multiplicado por el elemento de campo elegido. Entonces, $2^{p-1}$ es congruente a 1 módulo p.

De lo que no estoy seguro es del "sólo si". Si p es primo $2^{p-1} - 1$ es congruente a 0 módulo p. Sin embargo, esto no significa que si $2^{p-1} - 1$ es congruente a 0 módulo p, p es primo.

¿Puedes ayudarme a demostrar la parte de "sólo si"?

Por cierto, $2^{n-1} - 1$ es todo 1 en binario.

Answer 1

$561 = 3\cdot 11\cdot 17$ es compuesto, pero pasa su prueba (y también la pasa para cualquier base que no sea $2$ también).

Answer 2

SUGERENCIA. Números Carmichael para saber que estás equivocado. Agradezco sus esfuerzos y su entusiasmo.

Answer 3

Tu "prueba" no es determinista. Sí, se mantiene para todos los primos Impares $p$ que $2^{p-1} = 1 \pmod p$ Sin embargo Números de poulet también pasan la prueba y son compuestos. No podemos confiar en esto para probar que un número es primo, sin embargo, (para números grandes) es extremadamente probable que un número entero que satisfaga esta condición sea primo. GF $(p)$ es un campo finito con $p-1$ elementos cuando $p$ es primo. Es el campo de división del polinomio $X^p-X$ que contiene todos sus elementos como raíces. Otra forma de decirlo es:

$X^p-X$ es múltiplo de $p$ para todos los números enteros $X$ si $p$ es primo.

$X^p-X = 0 \pmod p$ .

$X^p = X \pmod p$ .

$X^{p-1} = 1 \pmod p$ siempre que $X ≠ 0 \pmod p$ .

Para esta última condición, sustituyendo el requisito de que $X ≠ 0 \pmod p$ con $\gcd(X, p)=1$ existen infinitos números enteros compuestos con las mismas propiedades (también conocidos como Números Carmichael ). Si desea que el $2^{p-1} \pmod p$ más potente y eficiente, debe utilizar una versión de la Prueba Miller Rabin para base 2.