En 1640, un gran matemático aficionado, Pierre de Fermat, formuló el llamado Pequeño Teorema de Fermat (no confunda con el Último Teorema de Fermat). Es una propiedad de los números primos y establece que para cualquier número primo [math] p [/ math] y un número arbitrario [math] a [/ math], entonces [math] a ^ pa [/ math] será divisible por [matemáticas] p [/ matemáticas]. No está nada claro por qué esto debería ser cierto, pero es válido para todos los números primos.
Más de 300 después, esta propiedad de los primos se volvió muy útil en muchas tecnologías modernas, algo con lo que Fermat ni siquiera soñó. De hecho, no es esta propiedad en particular, sino otras propiedades de los primos las que son tan útiles. Y se convirtió en una tarea importante para los matemáticos decidir si un número es primo o no.
Supongamos que le doy un número GRANDE, algo así como 1568456156486189856564564898761232654898948984894232138605600616187643225642221997 y le pregunto si este número es primo. Es una tarea difícil decidir sobre números tan grandes si son primos o no, y usamos números primos mucho más grandes que este todos los días, por ejemplo, al pagar con tarjeta, por lo que esta tarea también es muy importante.
- Cómo encontrar el área del triángulo curvo formado por [matemática] y = \ frac {pi} {6} [/ matemática], [matemática] y = \ tan ^ 2 x [/ matemática], [matemática] y = ( \ cot ^ 2 x) x [/ matemáticas]
- ¿Cuál es duodecimal y cómo es beneficioso utilizar en la vida cotidiana?
- Verdad matemática: ¿Qué hace que las oraciones matemáticas sean verdaderas?
- ¿Puedes tener un alto coeficiente intelectual pero ser mediocre o malo en matemáticas?
- ¿Cuál es la mayor paradoja matemática insoluble?
Una forma obvia de averiguar si un número [matemático] p [/ matemático] es primo o no es probar si es divisible por algún número menor, para hacerlo con un número de 80 dígitos, ya que solo necesita probar los divisores menos luego, la raíz cuadrada, deberías intentar con [math] 10 ^ {40} [/ math] divisiones. Suponga que puede probar [matemáticas] 10 ^ {10} [/ matemáticas] números por segundo, tendría que esperar [matemáticas] 10 ^ {30} [/ matemáticas] segundos, que es mucho más que la edad de nuestro universo .
Tenemos que probar algo más: usemos el pequeño teorema de Fermat. Elija un número aleatorio [matemática] a [/ matemática] y vea si [matemática] p [/ matemática] divide [matemática] a ^ pa [/ matemática]. Si no lo hace, [math] p [/ math] no es primo; sin embargo, si lo hace, puede o no ser primo, no puede estar seguro. Si intenta esto con diferentes valores de [math] a [/ math] y [math] p [/ math] pasa todas las pruebas, hay una buena probabilidad de que [math] p [/ math] sea primo, de ahí que se llama pseudoprime . Seudoprima de Fermat, en particular.
El problema es que existen los llamados números de Carmichael, y hay infinitos de ellos. Estos son números compuestos que pasan la prueba de Fermat para cada valor de [math] a [/ math] y, por lo tanto, no se pueden detectar en esta prueba. El más pequeño es 561.
Hay otras pruebas no deterministas (de hecho, la prueba de Fermat no se usa mucho en algoritmos reales) para la primalidad: cuando un número pasa esta prueba, hay una gran probabilidad de que sea primo, aunque no es cien por ciento. Pasar por estas pruebas se denominan pseudoprimos. Ver wikipedia para ejemplos más particulares Pseudoprime – Wikipedia.
