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^[1] de Carl Friedrich Gauss (1777 - 1855). O seu novo enfoque permite elucidar célebres conxecturas^[2] e simplifica as demostracións de importantes resultados^[3] 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 m ≥ 1, chamado módulo, dise que dous números enteiros a e b son congruentes módulo m, se m é un divisor da súa diferenza; é dicir, se hai un número enteiro k tal que

a − b = k m.

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

a ≡ b (mod m).

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

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

Como exemplo:

${\displaystyle 2=17\mod 5}$ onde 2 é o único menor residuo de 17 entre 5

${\displaystyle 2\equiv 17{\pmod {5}}}$ e tamén ${\displaystyle 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

a = k m + b,

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

a = p m + r,

b = q m + r,

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

Exemplos

No módulo 12 pódese afirmar que:

38 ≡ 14 (mod 12)

porque a diferenza é 38 − 14 = 24 = 2 × 12, un múltiplo de 12. Unha forma simple de entendelo é que 38 e 14 teñen o mesmo resto 2 cando se dividen por 12.

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

${\displaystyle {\begin{aligned}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{aligned}}}$

Propiedades básicas

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

• Reflexividade: a ≡ a (mod m)
• Simetría: a ≡ b (mod m) se b ≡ a (mod m).
• Transitividade: se a ≡ b (mod m) e b ≡ c (mod m), entón a ≡ c (mod m)

Se a₁ ≡ b₁ (mod m) e a ₂ ≡ b₂ (mod m), ou se a ≡ b (mod m), entón:^[4]

• a + k ≡ b + k (mod m) para calquera número enteiro k (compatibilidade coa translación)
• k a ≡ k b (mod m) para calquera número enteiro k (compatibilidade coa escala)
• k a ≡ k b (mod k m) para calquera número enteiro k
• a₁ + a₂ ≡ b₁ + b ₂ (mod m) (compatibilidade coa adición)
• a₁ − a₂ ≡ b₁ − b ₂ (mod m) (compatibilidade coa resta)
• a₁ a₂ ≡ b₁ b ₂ (mod m) (compatibilidade coa multiplicación)
• a^k ≡ b^k (mod m) para calquera número enteiro non negativo k (compatibilidade coa exponenciación)
• p(a) ≡ p(b) (mod m), para calquera polinomio p(x) con coeficientes enteiros (compatibilidade coa avaliación polinómica)

Se a ≡ b (mod m), entón é xeralmente falso que k^a ≡ k^b (mod m). Non obstante, o seguinte é certo:

• Se c ≡ d (mod φ(m)), onde φ é a función totiente de Euler, daquela a^c ≡ a^d (mod m) (sempre que a sexa coprimo con m).

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

• Se a + k ≡ b + k (mod m), onde k é calquera número enteiro, entón a ≡ b (mod m).
• Se k a ≡ k b (mod m) e k é coprimo con m, daquela a ≡ b (mod m).
• Se k a ≡ k b (mod k m) e k ≠ 0, entón a ≡ b (mod m).

A última regra pódese usar para trasladar a aritmética modular á división. Se b divide a, entón (a/b) mod m = (a mod b m) / b.

O inverso multiplicativo modular defínese polas seguintes regras:

• Existencia: existe un número enteiro denotado a⁻¹ tal que aa⁻¹ ≡ 1 (mod m) se e só se a é coprimo con m. Este número enteiro a⁻¹ chámase inverso multiplicativo modular de a módulo m.
• Se existen a ≡ b (mod m) e a⁻¹, entón a⁻¹ ≡ b⁻¹ (mod m) (compatibilidade co inverso multiplicativo, e, se a = b, unicidade módulo m).
• Se ax ≡ b (mod m) e a é coprimo a m, entón a solución a esta congruencia linear vén dada por x ≡ a⁻¹b (mod m).

O inverso multiplicativo x ≡ a⁻¹ (mod m) pódese calcular eficientemente resolvendo a ecuación de Bézout a x + m y = 1 para x, y, mediante o algoritmo de Euclides estendido.

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

Propiedades avanzadas

• Pequeno teorema de Fermat: se p é primo e non divide a, entón a ^p−1 ≡ 1 (mod p).
• Teorema de Euler: se a e m son primos primos, entón a ^φ(m) ≡ 1 (mod m), onde φ é función totiente de Euler.
• Unha simple consecuencia do pequeno teorema de Fermat é que se p é primo, entón a⁻¹ ≡ a^p−2 (mod p) é a inversa multiplicativa de 0 < a < p. De xeito máis xeral, a partir do teorema de Euler, se a e m son coprimos, entón a^{− 1} ≡ a^φ(m)−1 (mod m).
• Outra simple consecuencia é que se a ≡ b (mod φ(m)), onde φ é a función totiente de Euler, entón k^a ≡ k^b (mod m) sempre que k sexa coprimo con m.
• Teorema de Wilson: p é primo se e só se (p − 1)! ≡ −1 (mod p).
• Teorema chinés do resto: para calquera a, b e m, n coprimos, existe un único x (mod m n) tal que x ≡ a (mod m) e x ≡ b (mod n). De feito, x ≡ b m_n⁻¹ m + a n _m⁻¹ n (mod mn) onde m_n⁻¹ é a inversa de m módulo n e n_m⁻¹ é a inversa de n módulo m.
• Teorema de Lagrange: a congruencia f (x) ≡ 0 (mod p), onde p é primo e f (x) = a₀ x^m + ... + a_m é un polinomio con coeficientes enteiros tal que a₀ ≠ 0 (mod p), ten como máximo m raíces.
• Raíz primitiva módulo m: un número g é unha raíz primitiva módulo m se, para cada número enteiro a coprimo con m, hai un enteiro k tal que g^k ≡ a (mod m). Existe unha raíz primitiva módulo m se e só se m é igual a 2, 4, p ^k ou 2p^k, onde p é un número primo impar e k é un número enteiro positivo. Se existe unha raíz primitiva módulo m, entón hai exactamente φ(φ(m)) desas raíces primitivas, onde φ é a función totiente de Euler.
• Residuo cadrático: un enteiro a é un residuo cadrático módulo m, se existe un número enteiro x tal que x² ≡ a (mod m). O criterio de Euler afirma que, se p é un primo impar, e a non é múltiplo de p, entón a é un residuo cadrático módulo p se e só se

  a^(p−1)/2 ≡ 1 (mod p).

Clases de congruencia

A relación de congruencia é unha relación de equivalencia. A clase de equivalencia módulo m dun número enteiro a é o conxunto de todos os números enteiros da forma a + k m, onde k é calquera número enteiro. Chámase clase de congruencia ou clase de residuos de a módulo m, e pode ser denotado como (a mod m), ou como ${\displaystyle {\overline {a}}}$ ou [a] cando se coñece o módulo m polo contexto.

Cada clase de residuos módulo m contén exactamente un número enteiro no intervalo ${\displaystyle 0,...,|m|-1}$. Así, estes ${\displaystyle |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: ${\displaystyle {\overline {3}}=\{3,10,17,24,\ldots \}\in (3{\text{ mod }}7)}$ porque todos son igual a ${\displaystyle 3{\pmod {7}}}$, e pódense escribir como ${\displaystyle 3+7k}$. Normalmente escóllese como representante da clase o número ${\displaystyle r}$ que cumpre ${\displaystyle 0\leq r<m}$, que no exemplo sería o ${\displaystyle 3}$.

Enteiros módulo m

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

O conxunto de todas as clases de congruencia módulo m chámase anel de enteiros módulo m, e denótase ${\textstyle \mathbb {Z} /m\mathbb {Z} }$, ${\displaystyle \mathbb {Z} /m}$, ou ${\displaystyle \mathbb {Z} _{m}}$.^[5]. A notación ${\displaystyle \mathbb {Z} _{m}}$ non se recomenda porque se pode confundir co conxunto de enteiros m-ádicos. O anel ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ é fundamental en varias ramas das matemáticas.

Para m > 0 temos

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

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

• ${\displaystyle {\overline {a}}_{m}+{\overline {b}}_{m}={\overline {(a+b)}}_{m}}$
• ${\displaystyle {\overline {a}}_{m}-{\overline {b}}_{m}={\overline {(a-b)}}_{m}}$
• ${\displaystyle {\overline {a}}_{m}{\overline {b}}_{m}={\overline {(ab)}}_{m}.}$

As propiedades indicadas anteriormente implican que, con estas operacións, ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ é un anel conmutativo. Por exemplo, no anel ${\displaystyle \mathbb {Z} /24\mathbb {Z} }$, un ten

${\displaystyle {\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 ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ porque este anel é o anel cociente de ${\displaystyle \mathbb {Z} }$ polo ideal ${\displaystyle m\mathbb {Z} }$, o conxunto formado por todos os km con ${\displaystyle k\in \mathbb {Z} .}$

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

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

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

Notas

1. Carl Friedrich Gauss. Recherches arithmétiques, 1801 Tradución ó francés de M. Poullet-Delisle Éd. Courcier 1807
2. Por 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
3. Pódese citar o teorema de Wilson (p. 56), ou o pequeno teorema de Fermat (p. 50) de Recherches arithmétiques
4. Sandor Lehoczky; Richard Rusczky (2006). David Patrick, ed. the Art of Problem Solving (en inglés) 1 (7 ed.). AoPS Incorporated. p. 44. ISBN 0977304566. 
5. "2.3: Integers Modulo n". Mathematics LibreTexts (en inglés). 2013-11-16. Arquivado dende o orixinal o 2021-04-19. Consultado o 2020-08-12. 
6. Sengadir T., Aritmética modular en Google Books.

Véxase tamén

Wikimedia Commons ten máis contidos multimedia na categoría:  Aritmética modular

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. ISBN 0-262-03293-7. Section 31.3: Modular arithmetic, pp. 862–868.
• Anthony Gioia, Number Theory, an Introduction Reprint (2001) Dover. ISBN 0-486-41449-3.
• Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd ed.). Lexington: D. C. Heath and Company. LCCN 77171950. 
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory. Englewood Cliffs: Prentice Hall. ISBN 9780132683005. LCCN 71081766. 
• Sengadir, T. (2009). Discrete Mathematics and Combinatorics. Chennai, India: Pearson Education India. ISBN 978-81-317-1405-8. OCLC 778356123. 

Outros artigos

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

Ligazóns externas

• "Congruence". Encyclopedia of Mathematics. EMS Press. 2001 [1994]. 

• Modular Arithmetic and patterns in addition and multiplication tables