Para terminar la Unidad de Teoría de Números abordaremos dos problemas: Test de primalidad y los sistemas de congruencias.
Test de Primalidad
El segundo problema de los que añadimos como apéndice a la teoría de números es el de los test de primalidad.
Con anterioridad, vimos el teorema de Euler que nos determina el inverso, cuando existe, de un elemento en \(\mathbb{Z}_n\). Este teorema tenía un antecedente, que se conoce como el teorema pequeño de Fermat:
Si \(a,p\in\mathbb{Z}\) con \(p\) primo y \(p\) no divide a \(a\), entonces \[a^{p-1}\equiv 1\pmod{p}\]
Consecuentemente, si dado un número \(n\) que no divide a \(a\) se cumple \[a^{n-1}\not\equiv 1\pmod{n},\]
implicaría que \(n\) no es primo, pues de lo contrario incumpliría el teorema pequeño de Fermat.
Pues bien, este resultado lo podemos utilizar para chequear si un número es primo. Este test se denomina test de primalidad de Fermat.
Disponemos de un resultado que nos garantiza si un número es primo, el Teorema de Wilson:
El número \(n\in\mathbb{Z},\, n>1\) es primo si, y solo si, \[(n-1)!\equiv -1\pmod{n}\]
El problema es el cómputo del factorial, que es tremendamente costoso para números muy grandes. Por ese motivo utilizamos los test de primalidad.
Un test de primalidad (o chequeo de primalidad) es un algoritmo que, dado un número de entrada \(n\), no consigue verificar la hipótesis de un teorema cuya conclusión es que \(n\) es compuesto.
El test de Fermat nos propone buscar si un número es compuesto probando las igualdades
\[\begin{align*}2^{n-1}&\equiv 1\pmod{n},\\ 3^{n-1}&\equiv 1\pmod{n},\\ 5^{n-1}&\equiv 1\pmod{n},\\ &\ldots\\ a^{n-1}&\equiv 1\pmod{n},\end{align*}\] hasta encontrar un valor de \(1<a<n\) para el que no se cumpla.
Lo que ocurre es que podemos encontrar valores que verifican la igualdad siempre y no por ello son primos: son los conocidos números de Carmichael, o pseudoprimos.
Aplicación
El programa de cifrado PGP aprovecha esta propiedad del teorema para comprobar si los grandes números aleatorios que elige son primos. Comprueba los valores que llamaremos n utilizando 4 valores de a (llamados testigos) utilizando la fórmula anterior. Estos cuatro valores son 2, 3, 5 y 7, los cuatro primeros números primos. Si \[1 \equiv 2^{n-1}\equiv 3^{n-1} \equiv 5^{n-1} \equiv 7^{n-1} \pmod{n},\] entonces sabe que el número \(n\) es probablemente primo. Si de alguna de las expresiones anteriores se obtiene un valor distinto de 1, entonces n es definitivamente compuesto. Utilizar un número mayor de testigos disminuye la probabilidad de que un número compuesto \(n\) parezca primo. Estos números son los llamados pseudoprimos y entre ellos están los conocidos números de Carmichael.
Hay más test de este tipo; son conocidos como test probabilísticos de primalidad, pues no nos garantizan que es primo; más bien ofrecen una probabilidad de que sea primo.
El test de Fermat puede mejorarse utilizando el criterio de Euler:
Si \(p\in\mathbb{Z}\) es primo y \(p\) no divide a \(a\), entonces \[a^\frac{p-1}{2}\equiv 1\pmod{p}\, \mbox{ ó, } a^\frac{p-1}{2}\equiv -1\pmod{p}\]
El test probabilístico de primalidad más utilizado es el de Rabin-Miller, basado en el resultado:
Sea \(p\in\mathbb{Z},\, p>1\) primo impar y \(k,m\in\mathbb{Z}\), tales que \(p-1=2^km\), com \(m\) impar. Entonces, para todo entero positivo \(a\), menor que \(p\), se cumple al menos uno de los siguientes resultados:
- Algún número de la serie \(a^{2^km},a^{2^{k-1}m},\ldots,a^{m}\) es congruente con -1 módulo \(p\).
- \(a^m\equiv 1\pmod{p}\)
Sistemas de congruencias
Los sistemas de congruencias atienden al teorema chino del resto:
Supongamos que n1, n2, …, nk son enteros coprimos dos a dos. Entonces, para enteros dados a1,a2, …, ak, existe un entero x que resuelve el sistema de congruencias simultáneas
Más aún, todas las soluciones x de este sistema son congruentes módulo el producto N = n1n2…nk. La demostración y el método deductivo mediante el que se calcula la solución la tenéis en Teorema chino del resto.
Ejercicio: Resolver el sistema \[\begin{align*}
3X &\equiv 2\pmod{8} \\ 2X&\equiv 1\pmod{5} \end{align*}\]
| Ejercicio:Sean \(4x-11y+z=43\), \(7x+3y+5z=8\) y \((x_s,y_{s},z_s)\) la solución talque \(\text{min}\{0<z_{s}\}\). ¿Cuánto suma \(x_{s}+z_{s}\)? |