miniatura|200px|Cuberta da edición orixinal de Disquisitiones arithmeticae de Gauss, libro fundador da 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