Estaba leyendo acerca de Fermat poco Teorema, el cual establece que si p es primo, entonces para cualquier entero a, $a^p-a$ sería un múltiplo de p. Así que, empecé a wondeing si esto podría ser utilizado para determinar si un número p, fue el primer. En otras palabras, quería comprobar si la instrucción anterior se sostiene solamente si p es primo. Yo soy un programador, no un matemático, así que escribí un pequeño programa en Python.
for i in xrange(1, 101):
if ((3**i) - 3) % i == 0:
print i
Este programa recorre todos los números de 1 a 100 inclusive, y los enchufes en el teorema de Fermat como p. De una, yo he elegido 3. Impreso el siguiente (con varios números de poner en la misma línea por razones de brevedad):
1 2 3 5 6 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 66 67 71 73 79 83 89 91 97
Así, la salida contiene algunos vienen compuesto de números, pero estos parecen estar siempre múltiplos de 3. Así que he cambiado mi programa para excluir a los múltiplos de 3:
Y parece que funciona, solamente imprime los números primos. He intentado esto con un par de valores de un ahora, y estoy obteniendo los mismos resultados para todos ellos.
Así que esto me lleva a dos preguntas relacionadas:
- Se puede comprobar si un número p es primo mediante la comprobación de si $a^p - a$ es divisible por p, para un determinado tales que a y p son relativamente primos? Hay otras restricciones en una?
- Será el programa arriba mencionado alguna vez la impresión de un número compuesto, cuando se itera sobre todos los números naturales?
