Inverso multiplicativo modular

En matemáticas, particularmente na área da aritmética, o **inverso multiplicativo modular** dun número enteiro  é un número enteiro  tal que o produto  é congruente con 1 en relación ao módulo . Na notación estándar da aritmética modular esta congruencia escríbese como

: ax \equiv 1 \pmod{m},

que é a forma abreviada de escribir a afirmación de que  divide  a cantidade  ou, dito doutro xeito, o resto despois de dividir  polo número enteiro  é 1. Se  ten un inverso módulo , entón hai un número infinito de solucións desta congruencia, que forman unha clase de congruencia con respecto a este módulo. A maiores, calquera número enteiro que sexa congruente con  (é dicir,  clase de congruencia de a) ten calquera elemento da clase de congruencia de  como inverso multiplicativo modular. Usando a notación de \overline{w} para indicar a clase de congruencia que contén , isto pódese expresar dicindo que o *inverso multiplicativo modular* da clase de congruencia \overline{a} é a clase de congruencia \overline{x} tal que:

: \overline{a} \cdot_m \overline{x} = \overline{1},

onde o símbolo \cdot_m denota a multiplicación de clases de equivalencia módulo . Escrito deste xeito, represéntase claramente a analoxía co concepto habitual de inverso multiplicativo no conxunto de números racionais ou reais, substituíndo os números por clases de congruencia e alterando axeitadamente a operación binaria.

Do mesmo xeito que coa operación análoga sobre os números reais, un uso fundamental desta operación é resolver, cando sexa posíbel, congruencias lineares da forma

: ax \equiv b \pmod{m}.

## Aritmética modular 
Para un número enteiro positivo , dous enteiros,  e , dise que son **congruentes módulo ** se  divide a súa diferenza. Esta relación binaria denótase como

: a \equiv b \pmod{m}.

Isto é unha relación de equivalencia no conxunto de enteiros, \mathbb{Z}, e as clases de equivalencia chámanse **clases de congruencia módulo ** ou **clases de residuos módulo **. Denotamos \overline{a}  como a clase de congruencia que contén o número enteiro , daquela

: \overline{a} = \{b \in \mathbb{Z} \mid a \equiv b \pmod{m} \}.

Unha **congruencia linear** é unha congruencia modular da forma

: ax \equiv b \pmod{m}.

A diferenza das ecuacións lineares sobre os reais, as congruencias lineares poden ter cero, unha ou varias solucións. Se  é unha solución dunha congruencia linear, todo elemento en \overline{x} tamén é unha solución, polo que cando falamos do número de solucións dunha congruencia linear estamos a referirnos ao número de clases de congruencia diferentes que conteñen solucións.

Se  é o máximo común divisor de  e  entón a congruencia linear  ten solucións se e só se  divide a . Se  divide a , entón hai exactamente  solucións.

Un inverso multiplicativo modular dun número enteiro  con respecto ao módulo  é unha solución da congruencia linear

: ax \equiv 1 \pmod{m}.

O resultado anterior di que unha solución existe se e só se , é dicir,  e  deben ser primos relativos (é dicir, coprimos ou primos entre si). A maiores, cando se cumpre esta condición, hai exactamente unha solución, é dicir, cando existe, un inverso multiplicativo modular é único: Se  e  son ambos os dous inversos multiplicativos modulares de  en relación ao módulo , daquela

: ab \equiv ab' \equiv 1 \pmod{m} ,

polo tanto

: a(b-b') \equiv 0 \pmod{m}.

Se , entón , e  non terá un inverso multiplicativo modular. Polo tanto,  .

Cando  ten unha solución, a miúdo denótase coa notación habitual de inversos, expoñente -1

: x \equiv a^{-1} \pmod{m}.

### Números enteiros módulo  
A relación de congruencia, módulo , estabelece unha partición do conxunto de enteiros en  clases de congruencia. As operacións de suma e multiplicación pódense definir nestes  obxectos do seguinte xeito: Para sumar ou multiplicar dúas clases de congruencia, primeiro escolla un representante de cada clase e despois realice a operación habitual para os enteiros dos dous representantes. Finalmente, tome a clase de congruencia na que se atopa o resultado da operación enteira como resultado da operación sobre as clases de congruencia. En símbolos, con +_m e \cdot_m representando as operacións sobre clases de congruencia, estas definicións son

: \overline{a} +_m \overline{b} = \overline{a + b}

e

: \overline{a} \cdot_m \overline{b} = \overline{ab}.

Estas operacións están ben definidas, o que significa que o resultado final non depende das eleccións dos representantes que se fixeron para obter o resultado.

As  clases de congruencia con estas dúas operacións definidas forman un anel, chamado **anel de enteiros módulo **. Hai varias notacións utilizadas para estes obxectos alxébricos, a maioría das veces \mathbb{Z}/m\mathbb{Z} ou \mathbb{Z}/m (conxunto cociente), mais tamén \mathbb{Z}_m cando é improbábel a confusión con outros obxectos alxébricos.

As clases de congruencia dos enteiros módulo  coñecíanse tradicionalmente como *clases de residuos módulo m*, o que reflicte o feito de que todos os elementos dunha clase de congruencia teñen o mesmo resto (é dicir, "residuo") ao seren divididos por . O algoritmo de división para números enteiros mostra que o conxunto de números enteiros, {{Math|{0, 1, 2, ..., *m* − 1}}} forma un sistema completo de residuos módulo , coñecido como o **sistema de mínimos residuos módulo **.

### Grupo multiplicativo de enteiros módulo  
Non todos os elementos dun sistema de residuos completo módulo  teñen un inverso multiplicativo modular, por exemplo, cero nunca o ten. Despois de eliminar os elementos dun sistema de residuos completo que non son coprimos con , o que fica denomínase **sistema reducido de residuos**, cuxos elementos teñen todos un inverso multiplicativo modular. O número de elementos nun sistema reducido de residuos é \phi(m), onde \phi é a función totiente de Euler, é dicir, o número de enteiros positivos inferiores a  que son coprimos con .

Nun anel xeral con unidade non todos os elementos teñen un inverso multiplicativo e os que o teñen denomínanse **unidades**. Como o produto de dúas unidades é unha unidade, as unidades dun anel forman un grupo, o **grupo de unidades do anel** e moitas veces denótase como  se  é o nome do anel. O grupo de unidades do anel de enteiros módulo  chámase **grupo multiplicativo de enteiros módulo **, e é isomorfo a un sistema de residuos reducido. En particular, ten orde (tamaño), \phi(m).

No caso de que  sexa primo, digamos , daquela \phi(p) = p-1 e todos os elementos distintos de cero de \mathbb{Z}/p\mathbb{Z} teñen inversos multiplicativos, polo tanto \mathbb{Z}/p\mathbb{Z} é un corpo finito. Neste caso, o grupo multiplicativo de enteiros módulo  forma un grupo cíclico de orde .

## Exemplos 
* Para todo número enteiro n>1, sempre acontece que n^2-n+1 é o inverso multiplicativo modular de n+1  módulo n^2, xa que (n+1)(n^2-n+1)=n^3+1. Os exemplos son 3\times3 \equiv 1 \pmod{4}, 4\times7 \equiv 1 \pmod{9}, 5\times13 \equiv 1 \pmod{16}, etc.

* Dous números enteiros son congruentes mod 10 se e só se a súa diferenza é divisíbel por 10, por exemplo

: 32 \equiv 2 \pmod{10} xa que 10 divide 32 − 2 = 30, e
: 111 \equiv 1 \pmod{10} xa que 10 divide 111 − 1 = 110.

* A congruencia linear  non ten solucións xa que os enteiros que son congruentes con 5 (é dicir, os de \overline{5} ) son todos impares mentres que  sempre é par. No entanto, a congruencia linear  ten dúas solucións, a saber,  e . O  e temos que 2 non divide 5, mais si divide 6.

* Dado que , a congruencia linear  terá solucións, é dicir, existirán inversos multiplicativos modulares de 3 módulo 10. De feito, o 7 satisfai esta congruencia (é dicir, 21 − 1 = 20). 
:Por tanto 7 é un inverso multiplicativo de 3 módulo 10.

:Outros números enteiros tamén satisfán a congruencia, por exemplo 17 e −3 (é dicir, 3(17) − 1 = 50 e 3(−3) − 1 = −10). En particular, cada número enteiro en \overline{7} satisfará a congruencia xa que estes enteiros teñen a forma  para algún enteiro  e

: 3(7 + 10 r) - 1 = 21 + 30 r -1 = 20 + 30 r = 10(2 + 3r), 

:é divisíbel por 10. 

O produto das clases de congruencia \overline{5} e \overline{8} pódese obter seleccionando un elemento de \overline{5}, digamos 25, e un elemento de \overline{8}, digamos −2, e observando que o seu produto (25)(−2) = −50 está na clase de congruencia \overline{0}. Así, \overline{5} \cdot_{10} \overline{8} = \overline{0}. A suma defínese dun xeito similar. As dez clases de congruencia xunto con estas operacións de suma e multiplicación de clases de congruencia forman o anel de enteiros módulo 10, é dicir, \mathbb{Z}/10\mathbb{Z} .

## Cálculo 
### Algoritmo de Euclides estendido 
Pódese atopar un inverso multiplicativo modular  módulo  usando o algoritmo de Euclides estendido.

O algoritmo de Euclides determina números enteiros  e  que satisfán a identidade de Bézout,

: ax + my = \gcd(a, m)= 1.

Reescrito, isto é

: ax - 1 = (-y)m,

é dicir,

: ax \equiv 1 \pmod{m},

e polo tanto temos o inverso multiplicativo modular de . Unha versión máis eficiente do algoritmo é o algoritmo de Euclides estendido.

En notación O grande, este algoritmo corre en tempo , asumindo , e considérase moi rápido e xeralmente máis eficiente que a súa alternativa, a exponenciación.

### Usando o teorema de Euler 
Como alternativa ao algoritmo de Euclides estendido, o teorema de Euler pódese usar para calcular inversos modulares.

Segundo o teorema de Euler, se  é coprimo con , é dicir, , daquela

: a^{\phi(m)} \equiv 1 \pmod{m},

onde \phi é a función total de Euler. Isto débese ao feito de que  pertence ao grupo multiplicativo (\mathbb{Z}/m\mathbb{Z}) × se e só se  é coprimo con . Polo tanto, pódese atopar directamente un inverso multiplicativo modular mediante:

: a^{\phi(m)-1} \equiv a^{-1} \pmod{m}.

No caso especial onde  é primo, \phi (m) = m - 1 e o inverso modular vén dada por

: a^{-1} \equiv a^{m-2} \pmod{m}.

Este método é xeralmente máis lento que o algoritmo de Euclides estendido.

### Múltiples inversos 
É posíbel calcular a inversa de múltiples números , módulo un  común, cunha única invocación do algoritmo de Euclides e tres multiplicacións por entrada adicional.A idea básica é formar o produto de todos os , calcular a inversa e, a continuación, multiplica por  para todo  e así conseguir o desexado .

En pseudocódigo, o algoritmo é (toda a aritmética realizada módulo  ):

# Calcular os produtos prefixo b_i = \prod_{j=1}^i a_j = a_i b_{i-1} para todo .
# Calcula  usando calquera algoritmo coñecido.
# Para  desde  ata 2, calcuar
#* . 
#* .
# Finalmente, .

É posíbel realizar as multiplicacións nunha estrutura en árbore en lugar de utilizar de forma linear a computación paralela.

## Aplicacións 
No algoritmo RSA, o cifrado e descifrado dunha mensaxe realízase mediante un par de números que son inversos multiplicativos con respecto a un módulo coidadosamente seleccionado. Un destes números faise público e pódese utilizar nun procedemento de cifrado rápido, mentres que o outro, usado no procedemento de descifrado, manténse oculto. Determinar o número oculto a partir do número público considérase computacionalmente inviábel e isto é o que fai que o sistema funcione para garantir a privacidade.

Os inversos multiplicativos modulares utilízanse para obter unha solución dun sistema de congruencias lineares que está garantido polo teorema chinés do resto.

Por exemplo, o sistema

::  ≡ 4  (mod 5)
::  ≡ 4  (mod 7)
::  ≡ 6  (mod 11)

ten solucións comúns xa que 5,7 e 11 son coprimos por parellas. Unha solución vén dada por

:  =  (7 × 11) × 4 +  (5 × 11) × 4 +  (5 × 7) × 6

onde

:  = 3 é o inverso multiplicativo modular de 7 × 11 (mod 5),
:  = 6 é o inverso multiplicativo modular de 5 × 11 (mod 7),
:  = 6 é o inverso multiplicativo modular de 5 × 7 (mod 11).

Por tanto,

:  = 3 × (7 × 11) × 4 + 6 × (5 × 11) × 4 + 6 × (5 × 7) × 6 = 3504

e na súa forma reducida

:  ≡ 3504 ≡ 39 (mod 385)

xa que 385 é o mcm de 5,7 e 11.

Outro uso do inverso multiplicativo modular ocupa un lugar destacado na definición da suma de Kloosterman.

## Notas 
## Véxase tamén 
### Bibliografía 
* 
* 
* 
* 

### Outros artigos 
* Teorema chinés do resto.
* Aritmética modular.
* Anel (álxebra)
### Ligazóns externas 
*
* Calculadora en liña.