Congruencias y Aritmética Modular

La aritmética modular estudia los números enteros hasta la divisibilidad por un módulo fijo, transformando los enteros en el anillo finito Z/nZ y proporcionando a la teoría de números su herramienta computacional más flexible.

Definition

Dos enteros son congruentes módulo n si su diferencia es divisible por n. La aritmética modular es la aritmética de las clases de residuos resultantes, que forman el anillo conmutativo Z/nZ.

Scope

Este tema abarca la relación de congruencia y las clases de residuos, la aritmética en Z/nZ, las congruencias lineales y polinómicas, el teorema chino del resto, el pequeño teorema de Fermat y el teorema de Euler, la estructura del grupo de unidades, las raíces primitivas y el orden de los elementos. Es el lenguaje en el que se expresa la mayor parte de la teoría de números elemental y computacional.

Core questions

• ¿Cuándo tiene soluciones una congruencia lineal ax congruente con b mod n, y cuántas?
• ¿Cómo descompone el teorema chino del resto Z/nZ en un producto sobre módulos de potencias primas?
• ¿Por qué se cumplen el pequeño teorema de Fermat y el teorema de Euler, y qué dicen sobre el orden de las unidades?
• ¿Para qué módulos existe una raíz primitiva, haciendo cíclico el grupo de unidades?

Key theories

Teorema chino del resto

Si los módulos son coprimos por pares, un sistema de congruencias simultáneas tiene una solución única módulo el producto; equivalentemente, Z/nZ es isomorfo al producto de Z sobre sus factores de potencias primas.

Pequeño teorema de Fermat y teorema de Euler

Para a coprimo con n, a elevado a la función totiente de n es congruente con uno módulo n; el caso primo (Fermat) subyace a las pruebas de primalidad y el caso general subyace a RSA.

Raíces primitivas y estructura de grupo

El grupo multiplicativo de unidades mod n es cíclico exactamente cuando n es uno, dos, cuatro, una potencia de primo impar o el doble de una; un generador es una raíz primitiva, lo que da un logaritmo discreto.

Clinical relevance

La aritmética modular es el motor computacional de la criptografía (RSA, Diffie-Hellman, esquemas de curva elíptica), las sumas de comprobación y la detección de errores (ISBN, funciones hash), y la generación de números pseudoaleatorios, lo que la convierte en la parte más ampliamente desplegada de la teoría de números.

History

Aunque aparecen casos especiales en las matemáticas chinas e indias antiguas (el problema del resto que lleva el nombre de las primeras), la teoría sistemática de las congruencias fue introducida por Gauss en las Disquisitiones Arithmeticae (1801), donde estableció la notación y demostró los resultados estructurales centrales.

Key figures

• Carl Friedrich Gauss
• Pierre de Fermat
• Leonhard Euler

Seminal works

• irelandRosen1990

Frequently asked questions

¿Qué significa la notación a congruente con b mod n?

Significa que n divide la diferencia a menos b, o equivalentemente, a y b dejan el mismo resto al dividirlos por n.

¿Por qué RSA se basa en el teorema de Euler?

El cifrado y descifrado RSA son exponenciaciones modulares cuya composición devuelve el mensaje original precisamente porque el teorema de Euler garantiza que el exponente relevante actúa como la identidad módulo la clave.