El conjunto de los números primos es un subconjunto de los números naturales que engloba a todos los elementos de éste mayores que 1 que son divisibles únicamente por sí mismos y por la unidad. El teorema fundamental de la aritmética establece que cualquier número natural mayor que 1 siempre puede representarse como un producto de potencias de números primos, y esta representación (factorización) es única, por ejemplo en: 20 = 22-5 63 = 32-7 1.050 = 2-3-5 2-7. Todos los números primos, excepto el 2, son impares. Los únicos dos números primos consecutivos son el 2 y el 3. Los números primos impares consecutivos, es decir, aquellos que se hallan a una distancia numérica de 2 (por ejemplo, el 17 y el 19), se llaman números primos gemelos. Son de especial interés los números primos de Mersenne y los de Fermat. Un número primo es primo de Mersenne si al sumarle 1 el resultado es una potencia de 2. Por ejemplo, 7 es un número primo de Mersenne al cumplirse (7 + 1 = 8 = 23). Los ocho primeros números primos de Mersenne son, en consecuencia: 3, 7, 31, 127, 8191, 131071, 524287, 2147483647. En la actualidad se conocen apenas una cuarentena de números primos de Mersenne. Se trata de números gigantescos, como el 243112609 — 1, descubierto en 2008. A título de comparación, el número estimado de partículas elementales de todo el universo es inferior a 2300. Por su parte, un número primo de Fermat es un número primo de la forma: F = 22n +1, siendo n un número natural. Sólo se conocen cinco primos de Fermat: 3 (n = 0), 5 (n = 1), 17 (n = 2), 257 (n = 3) y 65.537 (n = 4). Los primos de Fermat llevan el nombre del ilustre jurista y matemático francés que los descubrió, Pierre de Fermat (1601-1665). El francés llevó a cabo numerosos e importantes descubrimientos adicionales relativos a los números primos, de entre los cuales destaca el conocido como pequeño teorema de Fermat, el cual establece que: Si p es un número primo entonces para cualquier entero a obtenemos que a^p = a en módulo p. Este resultado es de gran importancia en criptografía moderna, como se verá a continuación. De Euler a RSA Otro resultado de gran interés en aritmética modular es la conocida como identidad de Bézout. La identidad establece que si a y b son números enteros positivos, la igualdad mcd (a,b) = k equivale a que existen dos números enteros p, q que verifican pa + qb = k. En el caso particular de que mcd (a,b) = 1 tenemos que existen p y q enteros tales que pa + qb = 1. Si trabajamos en módulo n podemos establecer que si mcd (a,n) = 1 entonces existen, necesariamente, enteros p y q de manera que pa + qn= 1. Por la suposición de módulo n se tiene que qn = 0, con lo cual se concluye que existe un p de forma que pa = 1, es decir, el inverso de a en módulo n existe y es p. El número de elementos con inverso en módulo n será pues el número de naturales a menores que n que cumplen mcd(a,n) = 1. Este conjunto de números se conoce como función de Euler y se denota como φ(n). Si la descomposición de n en factores primos es n = p1^f1 p2^f2 ...pf^f, entonces: φ(n) = n(1-1/p1)(1-1/p2)...(1-1/pf) Si, por ejemplo, n = 1.600 = 2^5 5^2 tendremos que: φ(1.600) = 1.600(1-1/2)(1-1/5) = 640. Y afinando todavía más, si la situación es que n es primo se obtiene que para c