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

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.

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

• Primera Edición (15/02/2010) en Tito Eliatron Dixit.
• Segunda Edición (15/03/2010) en Juan de Mairena [v.2.71828].
• Tercera Edición (19/04/2010) en Geometría Dinámica.
• Cuarta Edición (17/05/2010) en Zurditorium.
• Quinta Edición (21/06/2010) en Ciencia por Barcedavid.
• Sexta Edición (27/09/2010) en Blog de Sangakoo.
• Séptima Edición (25/10/2010) en El Máquina de Turing.
• Octava Edición (21/11/2010) en Los Matemáticos no son gente seria.
• Novena Edición (20/12/2010) en Rescoldos en la trébede.
• Décima Edición (31/01/2011) en La Ciencia de la Mula Francis.

II

• Edición 2.1 (21/02/2011) en Tito Eliatron Dixit.
• Edición 2.2 (28/03/2011) en Gaussianos.
• Edición 2.3 (24/04/2011) en Los Matemáticos no son gente seria.
• Edición 2.4 (26/05/2011) en Seis Palabras Claras.
• Edición 2.5 (02/07/2011) en Juegos topológicos.
• Edición 2.6 (26/09/2011) en La Vaca Esférica.
• Edición 2.7 (25/10/2011) en La Aventura de la Ciencia.
• Edición 2.8 (29/11/2011) en Ciencia Conjunta.
• Edición 2.9 (26/12/2011) en Que no te aburran las M@tes.
• Edición 2.X (30/01/2012) en Resistencia Numantina.

III

• Edición 3.1 (28/02/2012) en Scientia potentia est.
• Edición 3.14 (26/03/2012) en Hablando de ciencia.
• Edición 3.141 (04/05/2012) en DesEquiLIBROS.
• Edición 3.1415 (29/05/2012) en Gaussianos.
• Edición 3.14159 (29/06/2012) en Scientia.
• Edición 3.141592 (01/10/2012) en ZTFNews.
• Edición 3.1415926 (29/10/2012) en Series divergentes.
• Edición 3.14159265 (02/12/2012) en Pimedios.
• Edición 3.141592653 (27/12/2012) en Que no te aburran las M@tes.
• Edición 3.1415926535 (30/01/2013) en La Aventura de la Ciencia.

IV

• Edición 4.1 (26/02/2013) en Tito Eliatron Dixit.
• Edición 4.12 (24/03/2013) en High Ability Dimension.
• Edición 4.123 (01/05/2013) en Eulerianos.
• Edición 4.1231 (27/05/2013) en Matemáticas interactivas y manipulativas.
• Edición 4.12310 (28/06/2013) en Geometría Dinámica.
• Edición 4.123105 (30/09/2013) en Cifras y Teclas.
• Edición 4.1231056 (02/11/2013) en Scientia.
• Edición 4.12310562 (29/11/2013) en ZTFNews.
• Edición 4.123105625 (02/01/2014) en Que no te aburran las M@tes.
• Edición 4.1231056256 (06/02/2014) en Cuentos Cuánticos.

V

• Edición 5.1 Rey Pastor (04/03/2014) en Tito Eliatron Dixit.
• Edición 5.2 Emmy Noether (31/03/2014) en MatesdeDavid.
• Edición 5.3 Felix Klein (27/04/2014) en Juegos topológicos.
• Edición 5.4 Martin Gardner (06/06/2014) en Gaussianos.
• Edición 5.5 Ronald Fisher (29/06/2014) en Pimedios.
• Edición 5.6 Paul Erdos (24/09/2014) en Cifras y Teclas.
• Edición 5.7 Alan Turing (30/10/2014) en El zombi de Schrödinger.
• Edición 5.8 Betty Scott (08/12/2014) en Tocamates.
• Edición 5.9 Enma Castelnuovo (29/12/2014) en Que no te aburran las M@tes.
• Edición 5.X Sofia Kovalévskaya (28/01/2015) en ZTFNews.

VI

• Edición 6.1 Números Perfectos (02/03/2015) en Tito Eliatron Dixit.
• Edición 6.2 Número Pi (03/04/2015) en La Aventura de la Ciencia.
• Edición 6.3 Teorema de Pitágoras (14/04/2015) en El mundo de Rafalillo.

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