{"id":886,"date":"2026-03-09T10:20:21","date_gmt":"2026-03-09T09:20:21","guid":{"rendered":"https:\/\/clases.jesussoto.es\/?p=886"},"modified":"2026-03-08T09:30:04","modified_gmt":"2026-03-08T08:30:04","slug":"mad-anexo-a-la-teoria-de-numeros","status":"publish","type":"post","link":"https:\/\/clases.jesussoto.es\/?p=886","title":{"rendered":"MAD: Anexo a la Teor\u00eda de n\u00fameros"},"content":{"rendered":"

Para terminar la Unidad de Teor\u00eda de N\u00fameros abordaremos dos problemas: Test de primalidad y los sistemas de congruencias.<\/p>\n

Test de Primalidad<\/h2>\n

El segundo problema de los que a\u00f1adimos como ap\u00e9ndice a la teor\u00eda de n\u00fameros es el de los test de primalidad.<\/p>\n

Con anterioridad, vimos el teorema de Euler que nos determina el inverso, cuando existe, de un elemento en \\(\\mathbb{Z}_n\\). Este teorema ten\u00eda un antecedente, que se conoce como el teorema peque\u00f1o de Fermat:<\/p>\n

\n

Si \\(a,p\\in\\mathbb{Z}\\) con \\(p\\) primo y \\(p\\) no divide a \\(a\\), entonces \\[a^{p-1}\\equiv 1\\pmod{p}\\]<\/p>\n<\/blockquote>\n

Consecuentemente, si dado un n\u00famero \\(n\\) que no divide a \\(a\\) se cumple \\[a^{n-1}\\not\\equiv 1\\pmod{n},\\]
\nimplicar\u00eda que \\(n\\) no es primo, pues de lo contrario incumplir\u00eda el teorema peque\u00f1o de Fermat.<\/p>\n

Pues bien, este resultado lo podemos utilizar para chequear si un n\u00famero es primo. Este test se denomina test de primalidad de Fermat.<\/p>\n

Disponemos de un resultado que nos garantiza si un n\u00famero es primo, el Teorema de Wilson:<\/p>\n

\n

El n\u00famero \\(n\\in\\mathbb{Z},\\, n>1\\) es primo si, y solo si, \\[(n-1)!\\equiv -1\\pmod{n}\\]<\/p>\n<\/blockquote>\n

El problema es el c\u00f3mputo del factorial, que es tremendamente costoso para n\u00fameros muy grandes. Por ese motivo utilizamos los test de primalidad.<\/p>\n

Un test de primalidad (o chequeo de primalidad) es un algoritmo que, dado un n\u00famero de entrada \\(n\\), no consigue verificar la hip\u00f3tesis de un teorema cuya conclusi\u00f3n es que \\(n\\) es compuesto.<\/p>\n

El test de Fermat nos propone buscar si un n\u00famero es compuesto probando las igualdades
\n\\[\\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.<\/p>\n

Lo que ocurre es que podemos encontrar valores que verifican la igualdad siempre y no por ello son primos: son los conocidos n\u00fameros de Carmichael, o pseudoprimos.<\/p>\n

Aplicaci\u00f3n<\/strong><\/h3>\n

El programa de cifrado PGP aprovecha esta propiedad del teorema para comprobar si los grandes n\u00fameros aleatorios que elige son primos. Comprueba los valores que llamaremos n utilizando 4 valores de a (llamados testigos) utilizando la f\u00f3rmula anterior. Estos cuatro valores son 2, 3, 5 y 7, los cuatro primeros n\u00fameros 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\u00famero \\(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\u00famero mayor de testigos disminuye la probabilidad de que un n\u00famero compuesto \\(n\\) parezca primo. Estos n\u00fameros son los llamados pseudoprimos y entre ellos est\u00e1n los conocidos n\u00fameros de Carmichael.<\/p>\n

\n

Hay m\u00e1s test de este tipo; son conocidos como test probabil\u00edsticos de primalidad, pues no nos garantizan que es primo; m\u00e1s bien ofrecen una probabilidad de que sea primo.<\/p>\n

El test de Fermat puede mejorarse utilizando el criterio de Euler:<\/p>\n

\n

Si \\(p\\in\\mathbb{Z}\\) es primo y \\(p\\) no divide a \\(a\\), entonces \\[a^\\frac{p-1}{2}\\equiv 1\\pmod{p}\\, \\mbox{ \u00f3, } a^\\frac{p-1}{2}\\equiv -1\\pmod{p}\\]<\/p>\n<\/blockquote>\n

El test probabil\u00edstico de primalidad m\u00e1s utilizado es el de Rabin-Miller, basado en el resultado:<\/p>\n

\n

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:<\/p>\n

    \n
  • Alg\u00fan n\u00famero de la serie \\(a^{2^km},a^{2^{k-1}m},\\ldots,a^{m}\\) es congruente con -1 m\u00f3dulo \\(p\\).<\/li>\n
  • \\(a^m\\equiv 1\\pmod{p}\\)<\/li>\n<\/ul>\n<\/blockquote>\n
    \n

    Sistemas de congruencias <\/h2>\n

    Los sistemas de congruencias atienden al teorema chino del resto:<\/p>\n

    Supongamos que n<\/em>1<\/sub>, n<\/em>2<\/sub>, \u2026, n<\/em>k<\/em><\/sub> son enteros coprimos dos a dos. Entonces, para enteros dados a<\/em>1<\/sub>,a<\/em>2<\/sub>, \u2026, a<\/em>k<\/em><\/sub>, existe un entero x<\/em> que resuelve el sistema de congruencias simult\u00e1neas<\/p>\n

    \n
    \"\\begin{align}<br<\/dd>\n<\/dl>\n

    M\u00e1s a\u00fan, todas las soluciones x<\/em> de este sistema son congruentes m\u00f3dulo el producto N<\/em> = n<\/em>1<\/sub>n<\/em>2<\/sub>\u2026n<\/em>k<\/em><\/sub>. La demostraci\u00f3n y el m\u00e9todo deductivo mediante el que se calcula la soluci\u00f3n la ten\u00e9is en Teorema chino del resto<\/a>.<\/p>\n