ÁLGEBRA

ARITMÉTICA MODULAR

módulo noetheriano es un módulo que satisface la condición de la cadena ascendente en sus submódulos, los cuales forman un orden parcial por inclusiones. Equivalentemente, los submódulos de un módulo noetheriano son finitamente generados, obviamente incluido él mismo.

El primer matemático que trabajó con las propiedades de submódulos finitamente generados fue el matemático alemán David Hilbert. A él se debe el conocido teorema de la base que dice que cualquier ideal de un anillo polinomial sobre un campo arbitrario es finitamente generado. Sin embargo, la propiedad es atribuida a la matemática alemana Emmy Noether, quien fue la primera en descubrir la importancia de la misma.

Caracterización[editar]

Con el uso del axioma de elección, un módulo ${\displaystyle M}$ es noetheriano si satisface las siguientes condiciones equivalentes:

• ${\displaystyle M}$ satisfice la condición de la cadena ascendente en sus submódulos.
• Cualquier conjunto ${\displaystyle S}$ no vacío de submódulos de ${\displaystyle M}$ tiene un elemento máximo, ordenados bajo inclusión. Es decir, ${\displaystyle M}$ contiene un submódulo ${\displaystyle M_{0}}$ tal que para todo elemento ${\displaystyle N}$ de ${\displaystyle S}$ que contenga ${\displaystyle M_{0}}$ tenemos que ${\displaystyle N=M_{0}}$.
• Todos los submódulos de ${\displaystyle M}$ son finitamente generados.

Ejemplos[editar]

• Todo anillo ${\displaystyle R}$ noetheriano es un módulo noetheriano sobre él mismo. Por ejemplo, los números enterosconsiderados como un ${\displaystyle \mathbb {Z} }$-módulo. En general si ${\displaystyle R}$ es un anillo noetheriano y ${\displaystyle M}$ es un módulo finitamente generado, entonces ${\displaystyle M}$ es noetheriano.
• Si ${\displaystyle R=M_{n}(K)}$ es el anillo de las matrices sobre un campo ${\displaystyle K}$, y ${\displaystyle M=M_{n\times 1}(K)}$ es el conjunto de los vectores columna sobre ${\displaystyle K}$, entonces ${\displaystyle M}$ es un ${\displaystyle R}$-módulo con la multiplicación de matrices. Este módulo es noetheriano.
• Todo módulo con un número finito de elementos es noetheriano.
• Todo módulo derecho finitamente generado sobre un anillo noetheriano es un módulo noetheriano. En particular, el teorema de la base de Hilbert nos dice que el anillo de polinomios de ${\displaystyle n}$-variables con coeficientes en un anillo noetheriano es un módulo noetheriano sobre el anillo.

Propiedades[editar]

Los módulos noetherianos se comportan bien en sucesiones exactas cortas, es decir dada una sucesión exacta corta de ${\displaystyle R}$-módulos

${\displaystyle 0\rightarrow M'\rightarrow M\rightarrow M''\rightarrow 0}$

entonces ${\displaystyle M}$ es noetheriano si y solamente si ${\displaystyle M'}$ y ${\displaystyle M''}$ son noetherianos.

La propiedad anterior no es cierta en general para módulos finitamente generados. Por ejemplo, un submódulo de un módulo finitamente generado puede no ser finitamente generado. Para ver esto consideremos el anillo ${\displaystyle R=\mathbb {Q} [X_{1},X_{2},X_{3},X_{4},\ldots ]}$ de los polinomios con infinitas variables sobre los números racionales, ${\displaystyle R}$ es un módulo finitamente generado sobre sí mismo; sin embargo el ideal ${\displaystyle I=(X_{1},X_{2},X_{3},X_{4},\ldots )}$ no es finitamente generado sobre ${\displaystyle R}$.

módulo libre es un módulo que tiene una base libre.

Para un R-módulo M, el conjunto E = {e₁, e₂... e_n} es una base libre para M si y sólo si:

1. E es un conjunto generador para M, es decir cada elemento de M es una suma de elementos de Emultiplicados por coeficientes en R.
2. si r₁e₁ + r₂ e₂ +... + r_n e_n = 0, entonces r₁ = r₂ =... = r_n = 0 (donde 0 es el elemento neutro de la suma en M y 0 el de R).

Si M tiene una base libre con n elementos, entonces M se dice libre de rango n, o más generalmente libre de rango finito. Observe que un corolario inmediato de (2) es que los coeficientes en (1) son únicos para cada x.

La definición de una base libre infinita es similar, aparte que E tendrá infinitamente muchos elementos. Pero, la suma debe ser una suma finita, y así que para cualquier x particular solamente finitamente muchos de los elementos de E están implicados.

En el caso de una base infinita, el rango de M es el cardinal de E.

 operación módulo obtiene el resto de la división de un número por otro ( a veces llamado módulo).¹​

Dados dos números positivos, a (el dividendo) y n (el divisor), a módulo n (abreviado como a mod n)^{nota 1}​ es el resto de la división euclídea de a por n. Por ejemplo, la expresión "5 mod 2" se evaluaría a 1 porque 5 dividido por 2 da un cociente de 2 y un resto de 1, mientras que "9 mod 3" se evaluaría a 0 porque la división de 9 entre 3 tiene un cociente de 3 y da un resto de 0.

el orden multiplicativo de a módulo n es el menor entero positivo k que cumple

a^k ≡ 1 (módulo n).

El orden de a (mód n) se suele denotar ord_n a, o bien O_n(a).

Por ejemplo, para determinar el orden multiplicativo de 4 módulo 7, calculamos 4² = 16 ≡ 2 (mód 7) y 4³ ≡ 64 ≡ 1 (mód 7), por tanto, ord₄(7) = 3.

Sin saber que estamos trabajando en un grupo finito, se puede demostrar que a tiene un orden si las potencias de a sólo pueden tomar un número finito de valores módulo n, por lo que debe haber dos exponentes, s y t, tales que a^s ≡ a^t (mód n). Como a y n son coprimos, esto implica que a^|s-t| ≡ 1 módulo n.

El concepto de orden multiplicativo es un caso especial del orden de elementos de un grupo. El orden multiplicativo de un número a módulo n es el orden de a en el grupo multiplicativo cuyos elementos son los residuos módulo n de los números coprimos con n, y cuya operación de grupo es la multiplicación módulo n. Este es el grupo de unidades del anillo Z_n; tiene φ(n) elementos (donde φ denota la función φ de Euler), y se denota por U(n) o U(Z_n).

Como consecuencia del teorema de Lagrange, ord_na siempre divide a φ(n). Si ord_n a es igual a φ(n) y por tanto tiene el valor máximo que puede tener, entonces a se dice raíz primitiva módulo n. Esto significa que el grupo U(n) es cíclico y la clase de residuos de a lo genera.

El pequeño teorema de Fermat es uno de los teoremas clásicos de teoría de números relacionado con la divisibilidad. Se formula de la siguiente manera:

Si p es un número primo, entonces, para cada número natural a, con a>0 , ap ≡ a (mod p) Pierre de Fermat, 1636

Aunque son equivalentes, el teorema suele ser presentado de esta otra forma:

Si p es un número primo, entonces, para cada número natural a, con a>0 , coprimo con p , ap-1 ≡ 1 (mod p) Pierre de Fermat, 1636

Esto quiere decir que, si se eleva un número a a la p-ésima potencia y al resultado se le resta a, lo que queda es divisible por p (véase aritmética modular). Su interés principal está en su aplicación al problema de la primalidady en criptografía.

Este teorema no tiene nada que ver con el legendario último teorema de Fermat, que fue sólo una conjeturadurante 350 años y finalmente fue demostrado por Andrew Wiles en 1995.

Historia[editar]

La civilización china parece que fue la primera cultura en estar interesada en la aritmética modular.²​ Existe una hipótesis,³​ documentada por Joseph Needham, según la cual los números de la forma 2^p − 2 fueron estudiados por esta civilización.

Así pues, matemáticos chinos formularon la hipótesis (a veces conocida como hipótesis china) de que p es primo si y sólo si 2^p ≡ 2 (mod p) (donde el símbolo ≡ significa congruencia según el módulo indicado). Es verdad que, si p es primo, entonces 2^p ≡ 2 (mod p) (este es un caso especial del pequeño teorema de Fermat), pero el recíproco (si 2^p ≡ 2 (mod p), entonces p es primo) no lo es, por lo que la hipótesis es falsa.

Se cree ampliamente que la hipótesis china fue desarrollada 2000 años antes del trabajo de Fermat en el siglo XVII. Aunque la hipótesis sea parcialmente incorrecta, es notable que pueda haber sido conocida por los matemáticos de la antigüedad. Algunos, sin embargo, sostienen que la creencia de que esta hipótesis fuera conocida hace tanto tiempo es fruto de un error de comprensión, y que se desarrolló realmente en 1872. Para más información sobre este asunto, consúltese Ribenboim, 1995.

Alrededor de 1636, Pierre de Fermat enunció el teorema. Aparece en una de sus cartas a su confidente Frénicle de Bessy, fechada el 18 de octubre de 1640, con el siguiente texto: p divide a a^p-1 - 1 cuando p sea primo y a sea coprimo con p.⁴​

Aunque actualmente lo conozcamos como pequeño teorema de Fermat, lo cierto es que hasta el siglo XX fue conocido como teorema de Fermat, como recoge por ejemplo Carl Friedrich Gauss en su libro Disquisitiones arithmeticae.⁵​ El término pequeño teorema de Fermat, tal como lo conocemos actualmente, fue usado por primera vez por el matemático alemán Kurt Hensel en 1913 en su libro Zahlentheorie.⁶​

Für jede endliche Gruppe besteht nun ein Fundamentalsatz, welcher der kleine Fermatsche Satz genannt zu werden pflegt, weil ein ganz spezieller Teil desselben zuerst von Fermat bewiesen worden ist.

He aquí el teorema fundamental que se cumple en cada grupo finito, llamado habitualmente pequeño teorema de Fermat, porque Fermat fue el primero en probar una parte especial de él.

Kurt Hensel

Demostración[editar]

Artículo principal: Demostraciones del pequeño teorema de Fermat

Fermat estableció tal resultado en una carta a Frénicle de Bessy, pero como era habitual en él, omitió la prueba del mismo:⁴​

Tout nombre premier mesure infailliblement une des puissances -1 de quelque progression que ce soit, et l’exposant de la dite puissance est sous-multiple du nombre premier donné -1. (...) Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.

Todo número primo mide una de las potencias menos uno de cualquier progresión en la que el exponente es un múltiplo del primo dado menos uno. (...) Y esta proposición es generalmente cierta para todas las progresiones y todos los números primos; le enviaría la prueba, si no temiese que es demasiado larga.

Pierre de Fermat

Leonhard Euler daría la primera demostraciónformal del teorema en 1736.

La primera demostración publicada se debe a Leonhard Euler en 1736 en un artículo titulado Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio.⁷​ Daría otras dos demostraciones más a lo largo de su vida,⁸​ aunque era la primera de todas ellas la misma que había en un manuscrito personal de Gottfried Leibniz, escrito sobre 1683 y que nunca llegó a publicar.⁹​ Gauss publicaría otra prueba más en su libro Disquisitiones arithmeticae en 1801.⁵​¹⁰​

La prueba original de Euler (y Leibniz) es sencilla, en términos de comprensión lógica, ya que sólo utiliza métodos elementales que una persona con nociones básicas de álgebra puede entender. Su demostración se basa en el principio de inducción, que consiste en demostrar que si cierta propiedad P de los números naturales se cumple para n y también se cumple para n+1, entonces se cumple para todo n.¹¹​ Es fácil ver que si se cumple para n, y para n+1, también se cumple para n+2, n+3, etc. ya que, llamando como n₁ a n+1, se cumple para n₁ y n₁+1, por tanto, para n, n+1 y n+2, y así sucesivamente.

Para la demostración también se utiliza la propiedad de que si p es un número primo, entonces el coeficiente binomial ${\displaystyle \textstyle {p \choose n}}$ es divisible por p, para todo n, tal que 1≤ n<p. Esto es así puesto que el coeficiente binomial se define como:

${\displaystyle {p \choose n}={\frac {p!}{(p-n)!\cdot n!}}}$

Donde el signo ! corresponde al factorial de un número, que indica la multiplicación de todos los números naturales menores o iguales a dicho número, por ejemplo, p! = p·(p-1)·(p-2)·...·2·1. Puesto que en eldenominador, los factoriales de los números involucran números que son menores que el número primo p, estos no pueden contener p ni dividir al número primo p del numerador, así pues, el coeficiente es divisible por p.

Dicho esto, la demostración consiste en los siguientes pasos:

• Supongamos que ${\displaystyle \textstyle {p\mid n^{p}-n}\,\!}$

• Utilizamos el binomio de Newton para expandir la potencia (n + 1)^p:

${\displaystyle (n+1)^{p}=\sum _{k=0}^{p}{p \choose k}n^{p-k}}$

• Agrupando factores y reordenando la identidad:

${\displaystyle (n+1)^{p}-(n+1)=n^{p}-n+\sum _{k=1}^{p-1}{p \choose k}n^{p-k}}$

• Por hipótesis, hemos supuesto que n^p - n es divisible por p, y dado que todos los términos del sumatorio del miembro de la derecha son divisibles por p, tenemos que p divide a (n + 1)^p - (n + 1).

• Ahora bien, 1^p - 1 es divisible por p, por lo tanto 2^p - 2 también es divisible por p, y así sucesivamente.

Q.E.D.

Ejemplos[editar]

A continuación se muestran algunos ejemplos del teorema:

• 5³ − 5 = 120 es divisible por 3.
• 7² − 7 = 42 es divisible por 2.
• 2⁵ − 2 = 30 es divisible por 5.
• (−3)⁷ + 3 = − 2.184 es divisible por 7.
• 2⁹⁷ − 2 = 158.456.325.028.528.675.187.087.900.672 es divisible por 97.
• Hallar el residuo de 8¹⁸⁷ (mod 13), aplicando el hecho de que 187 = 12·15 + 7 se simplifica, mediante el teorema de Fermat, a 8⁷, y al final se llega a 5 (mod13).

Aplicaciones[editar]

Las aplicaciones son numerosas, particularmente en criptografía. No obstante, hay ejemplos clásicos de aplicaciones del teorema en matemáticas puras, sobre todo, relacionadas con el problema de la primalidad.

Aplicaciones teóricas[editar]

El pequeño teorema de Fermat se ha utilizado históricamente para analizar la descomposición en producto de factores primos de ciertos enteros. Así, Fermat escribió a Marin Mersenne:¹²​

Vous me demandez si le nombre 100.895.598.169 est premier ou non, et une méthode pour découvrir, dans l'espace d'un jour, s'il est premier ou composé. A cette question, je réponds que ce nombre est composé et se fait du produit de ces deux: 898.423 et 112.303, qui sont premiers.

Usted me pregunta si el número 100.895.598.169 es primo o no, y un método para descubrir, en el plazo de un día, si es primo o compuesto. A esta pregunta, yo le respondo que este número es compuesto y que se obtiene del producto de estos dos: 898.423 y 112.303, que son primos.

Pierre de Fermat

Utilizando un método análogo, Euler invalidó la única conjetura falsa de Fermat, la cual decía que todo número de la forma F_n = 2²ⁿ + 1, (con n natural), es primo. (números de Fermat).¹³​

Este teorema también se ha utilizado para demostrar resultados de la teoría de números algebraicos, como el teorema de Herbrand-Ribet. Ha sobrepasado el ámbito estricto de la aritmética, con una utilización para el estudio de los puntos fijos del Endomorfismo de Frobenius, por ejemplo.

Criptografía asimétrica[editar]

Artículo principal: Criptografía asimétrica

La criptografía con clave pública corresponde a un código que se agrega para asegurar la confidencialidad de los mensajes con la ayuda de dos claves criptográficas. Una, que permite cifrar el mensaje, es pública. La otra, que tiene como objetivo el descifrado, es privada.

Una importante familia de códigos asimétricos utiliza la tecnología llamada RSA. La clave secreta está determinada por la descomposición de un número entero grande, a menudo de varias centenas de cifras. Este tiene dos factores primos. Lo esencial de las técnicas industriales de principios del siglo XXI se basa en el pequeño teorema de Fermat para generar grandes números primos o para comprobar la primalidad de un número.

Test de primalidad[editar]

Artículo principal: Test de primalidad

El pequeño teorema de Fermat da una condición necesaria para que un número p sea primo. Es necesario que, para todo número natural a menor que p, a^p-1 - 1 sea divisible por p, o sea, que a^p-1 sea congruente con unomódulo p (en notación moderna como a^{p - 1} ≡ 1 (mod p)). Este principio es la base del test de primalidad de Fermat.¹⁴​ Este test, al que asumimos una entrada n, consiste en ir probando que a^n-1 ≡ 1 (mod n) para una serie de valores de a, tales que sean menores que n. Si n es primo, entonces la congruencia se cumplirá siempre (condición necesaria del teorema) mientras que si n es compuesto, la congruencia puede no cumplirse. Si para algún valor de a (menor que n) no se cumple la congruencia, entonces n es compuesto. Una descripción de este test de forma general, en forma de algoritmo escrito en pseudocódigo, podría ser la siguiente:

Algoritmo Test de primalidad de Fermat.

Entrada: Un número natural n>1, el número k de veces que se ejecuta el test y nos determina la fiabilidad del test. Salida: COMPUESTO si n es compuesto y POSIBLE PRIMO si n es un posible primo. Para ${\displaystyle j\,\!}$ desde ${\displaystyle 1\,\!}$ hasta ${\displaystyle k\,\!}$ haga lo siguiente: ${\displaystyle a\gets }$ Función genera un número aleatorio comprendido entre ${\displaystyle 1\,\!}$ y ${\displaystyle n\,\!}$ (sin incluirlos) Si ${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$ entonces: Retorne COMPUESTO Retorne POSIBLE PRIMO

Existen numerosas variantes algorítmicas que usan como base este test. Las más conocidas son el test de primalidad de Solovay-Strassen y sobre todo el test de primalidad de Miller-Rabin.

Número pseudoprimo[editar]

Artículo principal: Número pseudoprimo

Los tests precedentes utilizan una condición necesaria pero no suficiente. Tanto es así que existen números enteros p compuestos y coprimos con a tal que a ^p-1 es congruente con uno modulo p, son los llamados pseudoprimos.¹⁵​ Estos números tienen la peculiaridad de que pueden pasar el test de primalidad de Fermatalgunas veces, siendo reconocidos como falsos primos. Existen varias clases de pseudoprimos, por ejemplo, los que cumplen que a^p-1 ≡ 1 (mod p) para todos los valores de a que sean coprimos con p, siendo p compuesto se denominan números de Carmichael. El número 1729 es un ejemplo de número de Carmichael. Además existen otros pseudoprimos que sólo se cumplen para una base a concreta, por ejemplo, si a es igual a 2, 341 cumple que 2^341-1 ≡ 1 (mod 341), siendo 341 claramente compuesto.

Los tests indicados en la sección anterior son todos estadísticos, en el sentido de que existe siempre una probabilidad, a veces muy débil, de que el número que ha pasado el test no es primo, debido a los pseudoprimoso al número de comprobaciones.

Generalizaciones[editar]

Una pequeña generalización del teorema, que se sigue de él, dice lo siguiente: si p es primo y m y n son enteros positivos con m ≡ n (mod p-1), entonces a^m ≡ aⁿ (mod p) para todos los enteros a.⁵​ Expresado así, el teorema se utiliza para justificar el método de cifrado de clave pública RSA.

El pequeño teorema de Fermat se puede generalizar mediante el teorema de Euler; para cualquier módulo n y cualquier entero a coprimo con n, se tiene:

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$

donde φ(n) es la función φ de Euler que cuenta el número de enteros entre 1 y n coprimos con n. Esta es de hecho una generalización, ya que si n = p es un número primo, entonces φ(p) = p - 1.

Aun así, todavía se puede generalizar más, como así se muestra en el teorema de Carmichael. Como antes, para cualquier módulo n y cualquier entero a coprimo con n, se tiene:

${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}$

donde ahora λ(n) es la función de Carmichael.