Inverso multiplicativo modular

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

${\displaystyle ax\equiv 1{\pmod {m}},}$

que é a forma abreviada de escribir a afirmación de que m divide a cantidade ax − 1 ou, dito doutro xeito, o resto despois de dividir ax polo número enteiro m é 1. Se a ten un inverso módulo m, 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 a (é dicir, a clase de congruencia de a) ten calquera elemento da clase de congruencia de x como inverso multiplicativo modular. Usando a notación de ${\displaystyle {\overline {w}}}$ para indicar a clase de congruencia que contén w, isto pódese expresar dicindo que o inverso multiplicativo modular da clase de congruencia ${\displaystyle {\overline {a}}}$ é a clase de congruencia ${\displaystyle {\overline {x}}}$ tal que:

${\displaystyle {\overline {a}}\cdot _{m}{\overline {x}}={\overline {1}},}$

onde o símbolo ${\displaystyle \cdot _{m}}$ denota a multiplicación de clases de equivalencia módulo m.^[2] 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

${\displaystyle ax\equiv b{\pmod {m}}.}$

Aritmética modular

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

${\displaystyle a\equiv b{\pmod {m}}.}$^[3]

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

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

Unha congruencia linear é unha congruencia modular da forma

${\displaystyle 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 x é unha solución dunha congruencia linear, todo elemento en ${\displaystyle {\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 d é o máximo común divisor de a e m entón a congruencia linear ax ≡ b (mod m) ten solucións se e só se d divide a b. Se d divide a b, entón hai exactamente d solucións.^[5]

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

${\displaystyle ax\equiv 1{\pmod {m}}.}$

O resultado anterior di que unha solución existe se e só se gcd(a, m) = 1, é dicir, a e m 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 b e b' son ambos os dous inversos multiplicativos modulares de a en relación ao módulo m, daquela

${\displaystyle ab\equiv ab'\equiv 1{\pmod {m}},}$

polo tanto

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

Se a ≡ 0 (mod m), entón gcd(a, m) = a, e a non terá un inverso multiplicativo modular. Polo tanto, b ≡ b' (mod m) .

Cando ax ≡ 1 (mod m) ten unha solución, a miúdo denótase coa notación habitual de inversos, expoñente ${\displaystyle -1}$

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

Números enteiros módulo m

A relación de congruencia, módulo m, estabelece unha partición do conxunto de enteiros en m clases de congruencia. As operacións de suma e multiplicación pódense definir nestes m 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 ${\displaystyle +_{m}}$ e ${\displaystyle \cdot _{m}}$ representando as operacións sobre clases de congruencia, estas definicións son

${\displaystyle {\overline {a}}+_{m}{\overline {b}}={\overline {a+b}}}$

e

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

As clases de congruencia dos enteiros módulo m 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 m. O algoritmo de división para números enteiros mostra que o conxunto de números enteiros, {0, 1, 2, ..., m − 1} forma un sistema completo de residuos módulo m, coñecido como o sistema de mínimos residuos módulo m.^[6]

Grupo multiplicativo de enteiros módulo m

Non todos os elementos dun sistema de residuos completo módulo m 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 m, 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 é ${\displaystyle \phi (m)}$, onde ${\displaystyle \phi }$ é a función totiente de Euler, é dicir, o número de enteiros positivos inferiores a m que son coprimos con m.

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 R^× se R é o nome do anel. O grupo de unidades do anel de enteiros módulo m chámase grupo multiplicativo de enteiros módulo m, e é isomorfo a un sistema de residuos reducido. En particular, ten orde (tamaño), ${\displaystyle \phi (m)}$.

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

Exemplos

• Para todo número enteiro ${\displaystyle n>1}$, sempre acontece que ${\displaystyle n^{2}-n+1}$ é o inverso multiplicativo modular de ${\displaystyle n+1}$ módulo ${\displaystyle n^{2}}$, xa que ${\displaystyle (n+1)(n^{2}-n+1)=n^{3}+1}$. Os exemplos son ${\displaystyle 3\times 3\equiv 1{\pmod {4}}}$, ${\displaystyle 4\times 7\equiv 1{\pmod {9}}}$, ${\displaystyle 5\times 13\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

${\displaystyle 32\equiv 2{\pmod {10}}}$ xa que 10 divide 32 − 2 = 30, e

${\displaystyle 111\equiv 1{\pmod {10}}}$ xa que 10 divide 111 − 1 = 110.

• A congruencia linear 4x ≡ 5 (mod 10) non ten solucións xa que os enteiros que son congruentes con 5 (é dicir, os de ${\displaystyle {\overline {5}}}$ ) son todos impares mentres que 4x sempre é par. No entanto, a congruencia linear 4x ≡ 6 (mod 10) ten dúas solucións, a saber, x = 4 e x = 9. O gcd(4, 10) = 2 e temos que 2 non divide 5, mais si divide 6.

• Dado que gcd(3, 10) = 1, a congruencia linear 3x ≡ 1 (mod 10) 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 ${\displaystyle 7}$ é un inverso multiplicativo de ${\displaystyle 3}$ módulo ${\displaystyle 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 ${\displaystyle {\overline {7}}}$ satisfará a congruencia xa que estes enteiros teñen a forma 7 + 10r para algún enteiro r e

${\displaystyle 3(7+10r)-1=21+30r-1=20+30r=10(2+3r),}$

é divisíbel por 10.

O produto das clases de congruencia ${\displaystyle {\overline {5}}}$ e ${\displaystyle {\overline {8}}}$ pódese obter seleccionando un elemento de ${\displaystyle {\overline {5}}}$, digamos 25, e un elemento de ${\displaystyle {\overline {8}}}$, digamos −2, e observando que o seu produto (25)(−2) = −50 está na clase de congruencia ${\displaystyle {\overline {0}}}$. Así, ${\displaystyle {\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, ${\displaystyle \mathbb {Z} /10\mathbb {Z} }$ .

Cálculo

Algoritmo de Euclides estendido

Pódese atopar un inverso multiplicativo modular a módulo m usando o algoritmo de Euclides estendido.

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

${\displaystyle ax+my=\gcd(a,m)=1.}$

Reescrito, isto é

${\displaystyle ax-1=(-y)m,}$

é dicir,

${\displaystyle ax\equiv 1{\pmod {m}},}$

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

En notación O grande, este algoritmo corre en tempo O(log²(m)), asumindo |a| < m, 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.^[7]

Segundo o teorema de Euler, se a é coprimo con m, é dicir, gcd(a, m) = 1, daquela

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

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

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

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

${\displaystyle 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 a_i, módulo un m común, cunha única invocación do algoritmo de Euclides e tres multiplicacións por entrada adicional.^[8]A idea básica é formar o produto de todos os a_i, calcular a inversa e, a continuación, multiplica por a_j para todo j ≠ i e así conseguir o desexado a−1
i.

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

1. Calcular os produtos prefixo ${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1}}$ para todo i ≤ n.
2. Calcula b−1
   n usando calquera algoritmo coñecido.
3. Para i desde n ata 2, calcuar
   • a−1
     i = b−1
     ib_i−1.
   • b−1
     i−1 = b−1
     ia_i.
4. Finalmente, a−1
   1 = b−1
   1.

É 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.^[9]

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

X ≡ 4 (mod 5)

X ≡ 4 (mod 7)

X ≡ 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

X = t₁ (7 × 11) × 4 + t₂ (5 × 11) × 4 + t₃ (5 × 7) × 6

onde

t₁ = 3 é o inverso multiplicativo modular de 7 × 11 (mod 5),

t₂ = 6 é o inverso multiplicativo modular de 5 × 11 (mod 7),

t₃ = 6 é o inverso multiplicativo modular de 5 × 7 (mod 11).

Por tanto,

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

e na súa forma reducida

X ≡ 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

1. Rosen 1993.
2. Schumacher 1996, p. 88.
3. Terence Tao usa habitualmente a notación sen a palabra "mod", ${\displaystyle a\equiv b\ (m).}$
4. Úsanse moitas veces outras notacións, incluíndo [a] e [a]_m.
5. Ireland & Rosen 1990
6. Ireland & Rosen 1990
7. Thomas Koshy. Elementary number theory with applications, 2nd edition. ISBN 978-0-12-372487-8. P. 346.
8. Brent, Richard P.; Zimmermann, Paul (December 2010). "§2.5.1 Several inversions at once" (PDF). Modern Computer Arithmetic. Cambridge Monographs on Computational and Applied Mathematics 18. Cambridge University Press. pp. 67–68. ISBN 978-0-521-19469-3. 
9. Trappe & Washington 2006

Véxase tamén

Bibliografía

• Ireland, Kenneth; Rosen, Michael (1990). A Classical Introduction to Modern Number Theory (2nd ed.). Springer-Verlag. ISBN 0-387-97329-X. 
• Rosen, Kenneth H. (1993). Elementary Number Theory and its Applications (3rd ed.). Addison-Wesley. ISBN 978-0-201-57889-8. 
• Schumacher, Carol (1996). Chapter Zero: Fundamental Notions of Abstract Mathematics. Addison-Wesley. ISBN 0-201-82653-4. 
• Trappe, Wade; Washington, Lawrence C. (2006). Introduction to Cryptography with Coding Theory (2nd ed.). Prentice-Hall. ISBN 978-0-13-186239-5. 

Outros artigos

• Teorema chinés do resto.
• Aritmética modular.
• Anel (álxebra)

Ligazóns externas

• Weisstein, Eric W. "Modular Inverse". MathWorld. 
• Calculadora en liña.