Aritmética modular

En matemáticas, e máis concretamente en teoría de números alxébricos, a aritmética modular é un conxunto de métodos que permiten a resolución de problemas sobre os números enteiros. Estes métodos xorden do estudo do residuo obtido por unha división.

A idea de base da aritmética modular é de traballar non sobre os números mesmos, senón sobre os residuos da súa división por algún outro número enteiro. Cando se fai, por exemplo, a proba do nove, efectúase unha operación de aritmética modular sen sabelo: o divisor é o valor 9.

Malia que as súas orixes se remontan á antigüidade, xeralmente, os historiadores asocian o seu nacemento co ano 1801, data da publicación do libro Disquisitiones ArithmeticaeCarl Friedrich Gauss. Recherches arithmétiques, 1801 Tradución ó francés de M. Poullet-Delisle Éd. Courcier 1807 de Carl Friedrich Gauss (1777 - 1855). O seu novo enfoque permite elucidar célebres conxecturasPor exemplo a lei de reciprocidade cadrática na páxina 96, ou a construción con regra e compás do heptadecágono nas páxinas 429-489 de Recherches arithmétiques e simplifica as demostracións de importantes resultadosPódese citar o teorema de Wilson (p. 56), ou o pequeno teorema de Fermat (p. 50) de Recherches arithmétiques grazas a unha maior abstracción. Se ben o eido natural destes métodos é a teoría dos números, as consecuencias das ideas de Gauss atópanse tamén noutros campos das matemáticas, como a álxebra ou a xeometría.

 Congruencia 
Dado un número enteiro , chamado módulo, dise que dous números enteiros  e  son congruentes módulo , se  é un divisor da súa diferenza; é dicir, se hai un número enteiro  tal que
 .
O módulo de congruencia  é unha relación de congruencia, o que significa que é unha relación de equivalencia que é compatible coas operacións de suma, resta e multiplicación. Denótase módulo de congruencia 
 .

As parénteses significan que  se aplica a toda a ecuación, non só ao lado dereito (aquí, ).

Existe un matiz de distinción coa notación  (sen parénteses), onde o resto de  cando se divide entre  denota o número enteiro único  tal que  e .

Como exemplo:
 onde 2 é o único menor residuo de 17 entre 5 
 e tamén  porque tanto 2, como 12, como 17 dan como residuo 2 cando se dividen entre 5.

A relación de congruencia pódese reescribir como
 ,
mostrando explicitamente a súa relación coa división euclidiana. Non obstante, o  aquí non ten por que ser o resto na división de  por . Máis ben,  afirma que  e  teñen o mesmo resto cando se divide entre . É dicir,
 ,
 ,
onde  é o resto común.
Como a congruencia módulo  está definida pola divisibilidade por  e como  é unha unidade no anel de enteiros, un número é divisible por  exactamente se é divisible por .
Isto significa que todo número enteiro distinto de cero  pode tomarse como módulo.

 Exemplos 
No módulo 12 pódese afirmar que:

porque a diferenza é , un múltiplo de . Unha forma simple de entendelo é que  e  teñen o mesmo resto  cando se dividen por .

A definición de congruencia tamén se aplica aos valores negativos. Por exemplo:


 Propiedades básicas 
A relación de congruencia satisfai todas as condicións dunha relación de equivalencia:
 Reflexividade: 
 Simetría:  se .
 Transitividade: se  e , entón 

Se  e , ou se , entón:
  para calquera número enteiro  (compatibilidade coa translación)
  para calquera número enteiro  (compatibilidade coa escala)
  para calquera número enteiro 
  (compatibilidade coa adición)
  (compatibilidade coa resta)
  (compatibilidade coa multiplicación)
  para calquera número enteiro non negativo  (compatibilidade coa exponenciación)
 , para calquera polinomio  con coeficientes enteiros (compatibilidade coa avaliación polinómica)

Se , entón é xeralmente falso que . Non obstante, o seguinte é certo:
 Se  onde  é a función totiente de Euler, daquela  (sempre que  sexa coprimo con ).

Para a cancelación de condicións comúns, temos as seguintes regras:
 Se , onde  é calquera número enteiro, entón .
 Se  e  é coprimo con , daquela .
 Se  e , entón .

A última regra pódese usar para trasladar a aritmética modular á división. Se  divide , entón .

O inverso multiplicativo modular defínese polas seguintes regras:
 Existencia: existe un número enteiro denotado  tal que  se e só se  é coprimo con . Este número enteiro  chámase inverso multiplicativo modular de  módulo .
 Se existen  e , entón  (compatibilidade co inverso multiplicativo, e, se , unicidade módulo ).
 Se  e  é coprimo a , entón a solución a esta congruencia linear vén dada por .

O inverso multiplicativo  pódese calcular eficientemente resolvendo a ecuación de Bézout   para , , mediante o algoritmo de Euclides estendido.

En particular, se  é un número primo, entón  é coprimo con  para cada  tal que ; polo tanto, existe un inverso multiplicativo para todos os  que non son congruentes con cero módulo .

 Propiedades avanzadas 
 Pequeno teorema de Fermat: se  é primo e non divide , entón  ≡ 1 (mod p).
 Teorema de Euler: se  e  son primos primos, entón  ≡ 1 (mod m), onde  é función totiente de Euler.
 Unha simple consecuencia do pequeno teorema de Fermat é que se  é primo, entón  (mod p)  é a inversa multiplicativa de . De xeito máis xeral, a partir do teorema de Euler, se  e  son coprimos, entón  ≡  (mod m).
 Outra simple consecuencia é que se , onde  é a función totiente de Euler, entón  sempre que  sexa coprimo con .
 Teorema de Wilson:  é primo se e só se .
 Teorema chinés do resto: para calquera ,  e ,  coprimos,  existe un único  tal que  e . De feito,  onde  é a inversa de  módulo  e  é a inversa de  módulo .
 Teorema de Lagrange: a congruencia , onde  é primo e  é un polinomio con coeficientes enteiros tal que , ten como máximo  raíces.
 Raíz primitiva módulo : un número  é unha raíz primitiva módulo  se, para cada número enteiro  coprimo con , hai un enteiro  tal que . Existe unha raíz primitiva módulo  se e só se  é igual a  ou , onde  é un número primo impar e  é un número enteiro positivo. Se existe unha raíz primitiva módulo , entón hai exactamente  desas raíces primitivas, onde  é a función totiente de Euler.
 Residuo cadrático: un enteiro  é un residuo cadrático módulo , se existe un número enteiro  tal que . O criterio de Euler afirma que, se  é un primo impar, e  non é múltiplo de , entón  é un residuo cadrático módulo  se e só se
  ≡ 1 (mod p).

 Clases de congruencia  
A relación de congruencia é unha relación de equivalencia. A clase de equivalencia módulo  dun número enteiro  é o conxunto de todos os números enteiros da forma , onde  é calquera número enteiro. Chámase clase de congruencia ou clase de residuos de  módulo , e pode ser denotado como , ou como  ou  cando se coñece o módulo  polo contexto.

Cada clase de residuos módulo  contén exactamente un número enteiro no intervalo . Así, estes  enteiros son representativos das súas respectivas clases de residuos.

Xeralmente é máis doado traballar con números enteiros que con conxuntos de números enteiros; é dicir, os representantes máis frecuentemente considerados, máis que as súas clases de residuos.

Por exemplo:  porque todos son igual a , e pódense escribir como . Normalmente escóllese como representante da clase o número  que cumpre , que no exemplo sería o .

 Enteiros módulo m 
Observación: no contexto desta sección, o módulo  tómase case sempre como positivo.

O conxunto de todas as clases de congruencia módulo  chámase anel de enteiros módulo , e denótase , , ou ..
A notación   non se recomenda porque se pode confundir co conxunto de enteiros -ádicos. O anel  é fundamental en varias ramas das matemáticas.

Para  temos

onde o trazo sobre o número ven a indicar os elementos da súa clase (todos os que teñen o mesmo residuo).

Se ,  é o anel cero; cando ,  non é un conxunto baleiro; máis ben, é isomorfo a , xa que .

A suma, a resta e a multiplicación defínense en  polas seguintes regras:




As propiedades indicadas anteriormente implican que, con estas operacións,  é un anel conmutativo. Por exemplo, no anel , un ten

como na aritmética para o reloxo de 24 horas.

Emprégase a notación  porque este anel é o anel cociente de  polo ideal , o conxunto formado por todos os  con 

Considerado como un grupo baixo adición,  é un grupo cíclico, e todos os grupos cíclicos son isomórfos con   para algún .Sengadir T., 

O anel de enteiros módulo  é un corpo se e só se  é un primo (isto garante que cada elemento distinto de cero ten un inverso multiplicativo). 

Se ,  denota o grupo multiplicativo dos números enteiros módulo  que son invertibles. Consta das clases de congruencia , onde  é coprimo a ; estas son precisamente as clases que posúen un inverso multiplicativo. Forman un grupo abeliano baixo multiplicación; a súa orde é , onde  é a función totiente de Euler.

 Notas 

 Véxase tamén 

 Bibliografía 
 John L. Berggren. "modular arithmetic". Encyclopædia Britannica.
 Maarten Bullynck "Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th-century Germany"
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 31.3: Modular arithmetic, pp. 862–868.
 Anthony Gioia, Number Theory, an Introduction'' Reprint (2001) Dover. .



 Outros artigos 
 Residuo cadrático.
 División.
 Lema de Hensel

 Ligazóns externas 


 Modular Arithmetic and patterns in addition and multiplication tables

Categoría:Teoría de números
Categoría:Álxebra abstracta