Aritmética modular

[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 Arithmeticae* de Carl Friedrich Gauss (1777 - 1855). O seu novo enfoque permite elucidar célebres conxecturas e simplifica as demostracións de importantes resultados 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:
: 2 = 17 \mod 5  onde 2 é o único menor residuo de 17 entre 5 
: 2 \equiv 17 \pmod 5  e tamén  12 \equiv 17 \pmod 5  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:
:  \begin{align}
2 &\equiv -3 \pmod 5\\
-8 &\equiv 7 \pmod 5\\
&  \text{ (o residuo de 7 entre 5 é 2, e o residuo de -8 entre 5 é -3, que ao restar de 5 tamén é 2) }\\ 
-3 &\equiv -8 \pmod 5.
\end{align}

## 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&nbsp;, e pode ser denotado como , ou como *\overline{a}* 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 0, ..., |m| - 1. Así, estes |m| 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:  \overline{3} = \{3, 10, 17, 24, \ldots\} \in (3 \text{ mod } 7)  porque todos son igual a 3 \pmod 7, e pódense escribir como 3 + 7k . Normalmente escóllese como representante da clase o número r que cumpre 0 \le r , que no exemplo sería o 3.

## 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 \mathbb{Z}/m\mathbb{Z}, \mathbb{Z}/m, ou \mathbb{Z}_m..
A notación \mathbb{Z}_m  non se recomenda porque se pode confundir co conxunto de enteiros -ádicos. O anel \mathbb{Z}/m\mathbb{Z} é fundamental en varias ramas das matemáticas.

Para  temos
: \mathbb{Z}/m\mathbb{Z} = \left\{ \overline{a}_m \mid a \in \mathbb{Z}\right\} = \left\{ \overline{0 }_m, \overline{1}_m, \overline{2}_m,\ldots, \overline{m{-}1}_m \right\},
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 , \mathbb{Z}/m\mathbb{Z} é o anel cero; cando , \mathbb{Z}/m\mathbb{Z} non é un conxunto baleiro; máis ben, é isomorfo a \mathbb{Z}, xa que .

A suma, a resta e a multiplicación defínense en \mathbb{Z}/m\mathbb{Z} polas seguintes regras:
* \overline{a}_m + \overline{b}_m = \overline{(a + b)}_m
* \overline{a}_m - \overline{b}_m = \overline{(a - b)}_m
* \overline{a}_m \overline{b}_m = \overline{(a b)}_m.

As propiedades indicadas anteriormente implican que, con estas operacións, \mathbb{Z}/m\mathbb{Z} é un anel conmutativo. Por exemplo, no anel \mathbb{Z}/24\mathbb{Z}, un ten
: \overline{12}_{24} + \overline{21}_{24} = \overline{33}_{24}= \overline{9}_{24}
como na aritmética para o reloxo de 24 horas.

Emprégase a notación \mathbb{Z}/m\mathbb{Z} porque este anel é o anel cociente de \mathbb{Z} polo ideal m\mathbb{Z}, o conxunto formado por todos os  con k\in\mathbb {Z}.

Considerado como un grupo baixo adición, \mathbb{Z}/m\mathbb{Z} é un grupo cíclico, e todos os grupos cíclicos son isomórfos con \mathbb{Z}/m\mathbb{Z}  para algún .

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 , (\mathbb Z/m\mathbb Z)^\times 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.&nbsp;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