Matemática Discreta/Aritmética Modular

Definición

editar

Se define cómo el residuo de una división no exacta donde

 

Donde 'r es un número natural y se vuelve el módulo del número,mientras que es el divisor b y a el número modulado siempre y cuando sean números enteros:

  y  

Quedando expresado cómo:

 

Historia

editar

En matemática, la aritmética modular es un sistema aritmético para clases de equivalencia de números enteros llamadas clases de congruencia. La aritmética modular fue introducida en 1801 por Carl Friedrich Gauss en su libro Disquisitiones Arithmeticae.[1]

Algunas veces se le llama, sugerentemente, aritmética del reloj, ya que los números «dan la vuelta» tras alcanzar cierto valor llamado módulo.[2]

Operaciones con Modulos

editar

Suma y Resta

editar

(+),Podemos definir las propiedades aritméticas para las sumas de congruencias:

Propiedad asociativa: a + (b + c) (mod (m)) = (a + b) + c (mod (m))

Elemento neutro: Existe un elemento 0 ∈ Zm, tal que a + 0 (mod (m)) = a (mod (m))

Elemento opuesto: Existe un elemento b ∈ Zm, tal que a + b = 0 (recordemos que 0 es el elemento neutro de la suma)

Propiedad conmutativa: a + b (mod (m)) = b + a (mod (m))

Multiplicación

editar

División

editar

Propiedades principales

editar

Clases de equivalencia módulo n

editar

La aritmética modular se basa en una relación de equivalencia, y las clases de equivalencia de un entero a se denota con [a]n (o simplemente [a] si sobreentendemos el módulo.) Otras notaciones son por ejemplo a + nZ o a mod n. El conjunto de todas las clases de equivalencia se denota con Z/nZ = { [0]n, [1]n, [2]n,..., [n-1]n }.[3]

Esta relación de equivalencia tiene importantes propiedades que se siguen inmediatamente de la definición:[3]

Si

 

y

 

entonces

 

y

 


Lo que muestra que la suma y la multiplicación son operaciones bien definidas sobre el conjunto de las clases de equivalencia. En otras palabras, la suma y la multiplicación están definidas sobre Z/nZ mediante las fórmulas siguientes:[3]

 
 

De este modo, Z/nZ se convierte en un anillo con n elementos. Por ejemplo, en el anillo Z/12Z, se tiene :[8]12[3]12 + [6]12 = [30]12 = [6]12.

El conjunto de enteros en Z/pZ forma un cuerpo finito si y sólo si p es primo.[4]

Resolución de congruencias

editar

Si a y b son enteros, la congruencia: axb (mod n) tiene solución x si y sólo si el máximo común divisor (a, n) divide a b. Los detalles están recogidos en el teorema de congruencia lineal. Sistemas de congruencias más complicados con módulos diferentes se pueden resolver usando el teorema chino del resto o el método de sustitución sucesiva.[5]

En el anillo de enteros, si consideramos la ecuación ax ≡ 1 (mod n), vemos que a tiene un inverso multiplicativo si y sólo si a y n son coprimos. Por tanto, Z/nZ es un cuerpo si y sólo si n es un primo.[6] Se puede probar que cada cuerpo finito es una extensión de Z/pZ para algún primo p.

Pequeño teorema de Fermat y teorema de Euler

editar

Un hecho importante sobre aritmética modular, cuando los módulos son números primos es el pequeño teorema de Fermat: si p es un número primo, entonces:[7]

Si a es cualquier entero:

 

Si a es un entero no divisible entre p:

 

Esto fue generalizado por Euler: para todo entero positivo n y todo entero a relativamente primo a n, :aφ(n) ≡ 1 (mod n), donde φ(n) denota función phi de Euler que cuenta el número de enteros entre 1 y n que sean coprimos con respecto a n.[8] El teorema de Euler es una consecuencia del teorema de Lagrange, aplicado al caso del grupo de las unidades del anillo Z/nZ.

Generalizaciones

editar

Dos enteros a, b son congruentes módulo n, escrito como:ab (mod n) si su diferencia ab es divisible entre n, esto es, si ab = kn para algún entero k.

Usando esta definición, podemos generalizar a módulos no enteros. Por ejemplo, podemos definir ab (mod 2π) si ab = k2π para algún entero k. Esta idea se desarrolla plenamente en el contexto de la teoría de los anillos y funciones trigonométricas.

En Álgebra abstracta se ve que la aritmética modular es un caso especial del proceso de crear un anillo factorial de un anillo módulo un ideal. Si R es un anillo conmutativo, e I es un ideal de R, entonces dos elementos a y b de R se dicen congruentes módulo I si ab es un elemento de I. Como pasaba con el anillo de enteros, esto se convierte en una relación de equivalencia, y la suma y la multiplicación se convierten en operaciones bien definidas sobre el anillo factorial R/I.

Fuentes

editar

http://gaussianos.com/teoria-de-numeros-elemental-aritmetica-modular/

https://es.wikipedia.org/wiki/Aritm%C3%A9tica_modular

https://es.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic

http://www.dma.fi.upm.es/recursos/aplicaciones/matematica_discreta/web/aritmetica_modular/

http://www.fiwiki.org/images/d/d3/MD_Tema3_AritmeticaModular.pdf

http://www.dma.fi.upm.es/recursos/aplicaciones/matematica_discreta/web/aritmetica_modular/congruencias.html

  1. Gauss, Carl Friedrich (1965). «Cap.1 Numbers congruences in general». Disquisitiones Arithmeticae. Yale University Press. ISBN 0-300-09473-6. . (Traducción al español)
  2. López, Jorge M. (28 de febrero de 2011). «Criptografía» (en castellano) (PDF). Consultado el 28 de febrero de 2011. 
    p.3
  3. 3,0 3,1 3,2 Carmona Collado, Luis Miguel. «Congruencias» (en castellano) (HTML). Introducción a la aritmética entera y modular. Consultado el 19 de abril de 2011.
  4. Kostrikin: Introducción al álgebra, Mir, Moscú (1974)
  5. Santiago Zaragoza, Antonio Cipriano (2009). «2.4. Congruencias lineales» (en castellano). Teoría de números (1ª edición). Madrid: Visión libros. pp. 22-25. ISBN 978-84-9886-360-4. 
  6. Navarro, Gabriel (2002). Universitat de València. ed (en castellano). Un curso de álgebra (1ª edición). Valencia. pp. 77. ISBN 84-370-5419-2. 
  7. Gauss, Carl Friedrich (1965). «Sec III, art. 50». Disquisitiones Arithmeticae. Yale University Press. ISBN 0-300-09473-6. . (Traducción al español)
  8. Euler, Leonhard « Theoremata circa residua ex divisione potestatum relicta », en Novi Comment. acad. sc. Petrop., vol. 7, 1761, p. 49-82. Texto original del latín Dartmouth College (Euler archive) con número E262. Traducción al inglés : Plantilla:Arxiv