Aritmética modular

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 Modelo:Math, chamado módulo, dise que dous números enteiros Modelo:Mvar e Modelo:Mvar son congruentes módulo Modelo:Mvar, se Modelo:Mvar é un divisor da súa diferenza; é dicir, se hai un número enteiro Modelo:Math tal que

Modelo:Math.

O módulo de congruencia Modelo:Mvar é 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 Modelo:Mvar

Modelo:Math.

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

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

Como exemplo:

$2=17mod5$ onde 2 é o único menor residuo de 17 entre 5

$2\equiv 17(\mathrm{mod}5)$ e tamén $12\equiv 17(\mathrm{mod}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

Modelo:Math,

mostrando explicitamente a súa relación coa división euclidiana. Non obstante, o Modelo:Math aquí non ten por que ser o resto na división de Modelo:Math por Modelo:Math. Máis ben, Modelo:Math afirma que Modelo:Math e Modelo:Math teñen o mesmo resto cando se divide entre Modelo:Math. É dicir,

Modelo:Math,

Modelo:Math,

onde Modelo:Math é o resto común. Como a congruencia módulo Modelo:Mvar está definida pola divisibilidade por Modelo:Mvar e como Modelo:Math é unha unidade no anel de enteiros, un número é divisible por Modelo:Math exactamente se é divisible por Modelo:Mvar. Isto significa que todo número enteiro distinto de cero Modelo:Mvar pode tomarse como módulo.

Exemplos

No módulo 12 pódese afirmar que:

Modelo:Math

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

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

$\begin{array}{cc}2& \equiv -3(\mathrm{mod}5)\\ -8& \equiv 7(\mathrm{mod}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(\mathrm{mod}5).\end{array}$

Propiedades básicas

A relación de congruencia satisfai todas as condicións dunha relación de equivalencia:

• Reflexividade: Modelo:Math
• Simetría: Modelo:Math se Modelo:Math.
• Transitividade: se Modelo:Math e Modelo:Math, entón Modelo:Math

Se Modelo:Math e Modelo:Math, ou se Modelo:Math, entón:

• Modelo:Math para calquera número enteiro Modelo:Math (compatibilidade coa translación)
• Modelo:Math para calquera número enteiro Modelo:Math (compatibilidade coa escala)
• Modelo:Math para calquera número enteiro Modelo:Math
• Modelo:Math (compatibilidade coa adición)
• Modelo:Math (compatibilidade coa resta)
• Modelo:Math (compatibilidade coa multiplicación)
• Modelo:Math para calquera número enteiro non negativo Modelo:Math (compatibilidade coa exponenciación)
• Modelo:Math, para calquera polinomio Modelo:Math con coeficientes enteiros (compatibilidade coa avaliación polinómica)

Se Modelo:Math, entón é xeralmente falso que Modelo:Math. Non obstante, o seguinte é certo:

• Se Modelo:Math onde Modelo:Math é a función totiente de Euler, daquela Modelo:Math (sempre que Modelo:Math sexa coprimo con Modelo:Math).

Para a cancelación de condicións comúns, temos as seguintes regras:

• Se Modelo:Math, onde Modelo:Math é calquera número enteiro, entón Modelo:Math.
• Se Modelo:Math e Modelo:Math é coprimo con Modelo:Math, daquela Modelo:Math.
• Se Modelo:Math e Modelo:Math, entón Modelo:Math.

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

O inverso multiplicativo modular defínese polas seguintes regras:

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

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

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

Propiedades avanzadas

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

  Modelo:Math ≡ 1 (mod p).

Clases de congruencia

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

Cada clase de residuos módulo Modelo:Math 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: $\bar{3}=\{3,10,17,24,\dots \}\in (3\text{ mod }7)$ porque todos son igual a $3(\mathrm{mod}7)$, e pódense escribir como $3+7k$. Normalmente escóllese como representante da clase o número $r$ que cumpre $0\le r<m$, que no exemplo sería o $3$.

Enteiros módulo m

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

O conxunto de todas as clases de congruencia módulo Modelo:Math chámase anel de enteiros módulo Modelo:Math, 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 [[Número p-ádico|Modelo:Math-ádicos]]. O anel $\mathbb{Z}/m\mathbb{Z}$ é fundamental en varias ramas das matemáticas.

Para Modelo:Math temos

$\mathbb{Z}/m\mathbb{Z}=\{{\bar{a}}_m\mid a\in \mathbb{Z}\}=\{{\bar{0}}_m,{\bar{1}}_m,{\bar{2}}_m,\dots ,{\overline{m-1}}_m\},$

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 Modelo:Math, $\mathbb{Z}/m\mathbb{Z}$ é o anel cero; cando Modelo:Math, $\mathbb{Z}/m\mathbb{Z}$ non é un conxunto baleiro; máis ben, é isomorfo a $\mathbb{Z}$, xa que Modelo:Math.

A suma, a resta e a multiplicación defínense en $\mathbb{Z}/m\mathbb{Z}$ polas seguintes regras:

• ${\bar{a}}_m+{\bar{b}}_m={\overline{(a+b)}}_m$
• ${\bar{a}}_m-{\bar{b}}_m={\overline{(a-b)}}_m$
• ${\bar{a}}_m{\bar{b}}_m={\overline{(ab)}}_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}={\bar{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 Modelo:Math 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 Modelo:Mvar.

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

Se Modelo:Math, $(\mathbb{Z}/m\mathbb{Z}{)}^{\times }$ denota o grupo multiplicativo dos números enteiros módulo Modelo:Math que son invertibles. Consta das clases de congruencia Modelo:Math, onde Modelo:Math é coprimo a Modelo:Math; estas son precisamente as clases que posúen un inverso multiplicativo. Forman un grupo abeliano baixo multiplicación; a súa orde é Modelo:Math, onde Modelo:Mvar é a función totiente de Euler.

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. Modelo:Isbn. Section 31.3: Modular arithmetic, pp. 862–868.
• Anthony Gioia, Number Theory, an Introduction Reprint (2001) Dover. Modelo:Isbn.
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro

Outros artigos

• Residuo cadrático.
• División.
• Lema de Hensel

Ligazóns externas

• Modelo:Springer

• Modular Arithmetic and patterns in addition and multiplication tables