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 algunha cousa. 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ópase tamén noutros campos das matemáticas, como a álxebra ou a xeometría.

Congruencia[editar | editar a fonte]

Dado un número enteiro $m \geq 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 \equiv b (mod m)

.

Os parénteses significan que $(mod m)$ aplícase 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 \leq r < m$ e $r \equiv b (mod m)$ .

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

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 \equiv 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 \leq 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[editar | editar a fonte]

No módulo 12 pódese afirmar que:

38 \equiv 14 (mod 12)

porque a diferenza é $38 - 14 = 24 = 2 \times 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:

{\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[editar | editar a fonte]

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

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

Se $a 1 \equiv b 1 (mod m)$ e $a 2 \equiv b 2 (mod m)$ , ou se $a \equiv b (mod m)$ , entón:^[4]

$a + k \equiv b + k (mod m)$ para calquera número enteiro $k$ (compatibilidade coa translación)
$k a \equiv k b (mod m)$ para calquera número enteiro $k$ (compatibilidade coa escala)
$k a \equiv k b (mod k m)$ para calquera número enteiro $k$
$a 1 + a 2 \equiv b 1 + b 2 (mod m)$ (compatibilidade coa adición)
$a 1 - a 2 \equiv b 1 - b 2 (mod m)$ (compatibilidade coa resta)
$a 1 a 2 \equiv b 1 b 2 (mod m)$ (compatibilidade coa multiplicación)
$a k \equiv b k (mod m)$ para calquera número enteiro non negativo $k$ (compatibilidade coa exponenciación)
$p (a) \equiv p (b) (mod m)$ , para calquera polinomio $p (x)$ con coeficientes enteiros (compatibilidade coa avaliación polinómica)

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

Se $c \equiv d (mod φ (m)),$ onde $φ$ é a función totiente de Euler, daquela $a c \equiv 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 \equiv b + k (mod m)$ , onde $k$ é calquera número enteiro, entón $a \equiv b (mod m)$ .
Se $k a \equiv k b (mod m)$ e $k$ é coprimo con $m$ , daquela $a \equiv b (mod m)$ .
Se $k a \equiv k b (mod k m)$ e $k \neq 0$ , entón $a \equiv 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 -1$ tal que $aa -1 \equiv 1 (mod m)$ se e só se $a$ é coprimo con $m$ . Este número enteiro $a -1$ chámase inverso multiplicativo modular de $a$ módulo $m$ .
Se existen $a \equiv b (mod m)$ e $a -1$ , entón $a -1 \equiv b -1 (mod m)$ (compatibilidade co inverso multiplicativo, e, se $a = b$ , unicidade módulo $m$ ).
Se $ax \equiv b (mod m)$ e $a$ é coprimo a $m$ , entón a solución a esta congruencia linear vén dada por $x \equiv a -1 b (mod m)$ .

O inverso multiplicativo $x \equiv a -1 (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[editar | editar a fonte]

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 -1 \equiv 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 \equiv b (mod φ (m))$ , onde $φ$ é a función totiente de Euler, entón $k a \equiv k b (mod m)$ sempre que $k$ sexa coprimo con $m$ .
Teorema de Wilson: $p$ é primo se e só se $(p - 1)! \equiv -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 \equiv a (mod m)$ e $x \equiv b (mod n)$ . De feito, $x \equiv b m n -1 m + a n m -1 n (mod mn)$ onde $m n -1$ é a inversa de $m$ módulo $n$ e $n m -1$ é a inversa de $n$ módulo $m$ .
Teorema de Lagrange: a congruencia $f (x) \equiv 0 (mod p)$ , onde $p$ é primo e $f (x) = a 0 x m + ... + a m$ é un polinomio con coeficientes enteiros tal que $a 0 \neq 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 \equiv a (mod m)$ . Existe unha raíz primitiva módulo $m$ se e só se $m$ é igual a $2, 4, p k$ ou $2 p 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 2 \equiv 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).

Enteiros módulo m[editar | editar a fonte]

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

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

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 {(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}={\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 $km$ 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 $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$ , $(\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[editar | editar a fonte]

↑ Carl Friedrich Gauss. Recherches arithmétiques, 1801 Tradución ó francés de M. Poullet-Delisle Éd. Courcier 1807
↑ 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
↑ Pódese citar o teorema de Wilson (p. 56), ou o pequeno teorema de Fermat (p. 50) de Recherches arithmétiques
↑ 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.
↑ "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.
↑ Sengadir T., Aritmética modular en Google Books.