“Edición 6.4: pseudoprimos” del Carnaval de Matemáticas (20-27 de mayo)

carnaval-de-matem64jpg De nuevo pimedios se siente agradecido de albergar una nueva edición del Carnaval de Matemáticas. En esta ocasión la Edición 6.4 se dedica a los pseudoprimos.

La fascinación por los números primos ha cautivado a  los matemáticos desde los principios de la matemática. Euclides fue el primero en buscar propiedades, pero el gran salto se produjo tras la reaparición de la obra Arithmetica de Diofanto de Alejandría. Esta obra serviría de inspiración para el gran gestor de la teoría de números actual: Pierre de Fermat.

Pierre de Fermat.jpg
«Pierre de Fermat» por http://www-groups.dcs.st-and.ac.uk/~history/PictDisplay/Fermat.html. Disponible bajo la licencia Dominio público vía Wikimedia Commons.

Este jurista francés y aficionado a las matemáticas, encontró en 1636 una propiedad que cumplían los números primos(Teorema pequeño de Fermat):

Si $p$ es primo y no divide a un entero $a$>0 entonces divide a  $a^p-a$

Este resultado lleva implícito una prueba para determinar que un número no es primo: si $n$ y $a$ son coprimos y  $a^{p-1}\not\equiv 1(mod\, n) $, entonces $n$ no pude ser primo. Pero, ¿qué ocurre si $a^{p-1}\equiv 1(mod\, n) $?, ¿podemos afirmar que $n$ es primo? La respuesta es que no. Sólo existe un resultado así de simple que nos ofrezca una condición de primalidad: el Teorema de Wilson.

Aún así el Teorema pequeño de Fermat nos ofrece una posibilidad más sencilla de estudiar la primalidad que el Teorema de Wilson. Si un número cumple el teorema es un buen candidato a ser primo. De modo que podemos utilizar el teorema como un test para determinar los candidatos a ser primos. Si además utilizamos como $a$, en el teorema, los números primos menores, será más fuerte y constituiremos el test de primalidad de Fermat.  A estos candidatos que superen el test se les denomina pseudoprimos o pseudoprimos de Fermat. Formalmente, los pseudoprimos son aquellos números que no siendo primos, verifican el Teorema pequeño de Fermat de base b. El programa de cifrado PGP utiliza este test para comprobar si los grandes números aleatorios que elige son primos.

Si cambiamos la base a la que sometemos un número $n$ y sigue superando el test, la probabilidad de que sea primo aumenta considerablemente. En 1912 Robert Daniel Carmichael probó que existen pseudoprimos que verifican el test para cualquier base. Estos pseudoprimos especiales se les denomina números de Carmichael.

Así presentamos la Edición 6.4: pseudoprimos del Carnaval de Matemáticas, que se celebrará entre el 20 y 27 de mayo, ambos incluidos. Entre el 28 y 30 de mayo se publicará el resumen del Carnaval.

El procedimiento para participar es sencillo: escribir una entrada, de tema libre, en un blog, que esté relacionada con las matemáticas (la entrada que no el blog). Deberéis hacer constar que la entrada participa en el Carnaval,  mencionando la edición y un enlace a esta entrada que os convoca; por ejemplo,

Esta entrada participa en la Edición 6.4: pseudoprimos del Carnaval de Matemáticas cuyo anfitrión es pimedios.

Para que pueda localizaros con facilidad y realizar el resumen correctamente, os pediré que me indiquéis vuestra participación de una de estas dos formas:

  • Mediante un comentario en esta misma entrada con un enlace a tu aportación.
  • Por Twitter incluyendo la etiqueta #CarnaMat64 y que haga mención a mi cuenta (@pimediosEs).

Como recuerdo os dejo las ediciones que se han celebrado hasta ahora:

I

II

III

IV

V

VI

¡Ale!, a trabajar y que los pseudoprimos os inspiren.

20 comentarios

  1. Buenas!

    Cuenta con mi habitual participación en el Carnaval.

    Por cierto, acabo de publicar el resumen del mes anterior, del cual he sido anfitrión, así que ya puedes actualizar el enlace a mi blog con dicho resumen. Y otra cosilla, en el párrafo en el que indicas el plazo para participar te has equivocado al referirte a tu edición como la 6.3 en vez de la 6.4.

    Muchas gracias por albergar la nueva edición 😉

Los comentarios están cerrados.