Inverso multiplicativo modular

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

$ax\equiv 1(\mathrm{mod}m),$

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

$\bar{a}{\cdot }_m\bar{x}=\bar{1},$

onde o símbolo ${\cdot }_m$ denota a multiplicación de clases de equivalencia módulo Modelo:Mvar. 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(\mathrm{mod}m).$

Aritmética modular

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

$a\equiv b(\mathrm{mod}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 Modelo:Mvar ou clases de residuos módulo Modelo:Mvar. Denotamos $\bar{a}$ como a clase de congruencia que contén o número enteiro Modelo:Mvar, daquela

$\bar{a}=\{b\in \mathbb{Z}\mid a\equiv b(\mathrm{mod}m)\}.$

Unha congruencia linear é unha congruencia modular da forma

$ax\equiv b(\mathrm{mod}m).$

A diferenza das ecuacións lineares sobre os reais, as congruencias lineares poden ter cero, unha ou varias solucións. Se Modelo:Mvar é unha solución dunha congruencia linear, todo elemento en $\bar{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 Modelo:Mvar é o máximo común divisor de Modelo:Mvar e Modelo:Mvar entón a congruencia linear Modelo:Math ten solucións se e só se Modelo:Mvar divide a Modelo:Mvar. Se Modelo:Mvar divide a Modelo:Mvar, entón hai exactamente Modelo:Mvar solucións.

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

$ax\equiv 1(\mathrm{mod}m).$

O resultado anterior di que unha solución existe se e só se Modelo:Math, é dicir, Modelo:Mvar e Modelo:Mvar 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 Modelo:Mvar e Modelo:Mvar son ambos os dous inversos multiplicativos modulares de Modelo:Mvar en relación ao módulo Modelo:Mvar, daquela

$ab\equiv a{b}^{\prime }\equiv 1(\mathrm{mod}m),$

polo tanto

$a(b-b^{\prime })\equiv 0(\mathrm{mod}m).$

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

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

$x\equiv a^{-1}(\mathrm{mod}m).$

Números enteiros módulo Modelo:Mvar

A relación de congruencia, módulo Modelo:Mvar, estabelece unha partición do conxunto de enteiros en Modelo:Mvar clases de congruencia. As operacións de suma e multiplicación pódense definir nestes Modelo:Mvar 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

$\bar{a}{+}_m\bar{b}=\overline{a+b}$

e

$\bar{a}{\cdot }_m\bar{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 Modelo:Mvar clases de congruencia con estas dúas operacións definidas forman un anel, chamado anel de enteiros módulo Modelo:Mvar. 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 Modelo:Mvar 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 Modelo:Mvar. O algoritmo de división para números enteiros mostra que o conxunto de números enteiros, Modelo:Math} forma un sistema completo de residuos módulo Modelo:Mvar, coñecido como o sistema de mínimos residuos módulo Modelo:Mvar.

Grupo multiplicativo de enteiros módulo Modelo:Mvar

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

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 Modelo:Math se Modelo:Mvar é o nome do anel. O grupo de unidades do anel de enteiros módulo Modelo:Mvar chámase grupo multiplicativo de enteiros módulo Modelo:Mvar, e é isomorfo a un sistema de residuos reducido. En particular, ten orde (tamaño), $\varphi (m)$.

No caso de que Modelo:Mvar sexa primo, digamos Modelo:Mvar, daquela $\varphi (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 Modelo:Mvar forma un grupo cíclico de orde Modelo:Math.

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\times 3\equiv 1(\mathrm{mod}4)$, $4\times 7\equiv 1(\mathrm{mod}9)$, $5\times 13\equiv 1(\mathrm{mod}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(\mathrm{mod}10)$ xa que 10 divide 32 − 2 = 30, e

$111\equiv 1(\mathrm{mod}10)$ xa que 10 divide 111 − 1 = 110.

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

• Dado que Modelo:Math, a congruencia linear Modelo:Math 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 $\bar{7}$ satisfará a congruencia xa que estes enteiros teñen a forma Modelo:Math para algún enteiro Modelo:Mvar e

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

é divisíbel por 10.

O produto das clases de congruencia $\bar{5}$ e $\bar{8}$ pódese obter seleccionando un elemento de $\bar{5}$, digamos 25, e un elemento de $\bar{8}$, digamos −2, e observando que o seu produto (25)(−2) = −50 está na clase de congruencia $\bar{0}$. Así, $\bar{5}{\cdot }_{10}\bar{8}=\bar{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 Modelo:Mvar módulo Modelo:Mvar usando o algoritmo de Euclides estendido.

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

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

Reescrito, isto é

$ax-1=(-y)m,$

é dicir,

$ax\equiv 1(\mathrm{mod}m),$

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

En notación O grande, este algoritmo corre en tempo Modelo:Math, asumindo Modelo:Math, 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 Modelo:Mvar é coprimo con Modelo:Mvar, é dicir, Modelo:Math, daquela

$a^{\varphi (m)}\equiv 1(\mathrm{mod}m),$

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

$a^{\varphi (m)-1}\equiv a^{-1}(\mathrm{mod}m).$

No caso especial onde Modelo:Mvar é primo, $\varphi (m)=m-1$ e o inverso modular vén dada por

$a^{-1}\equiv a^{m-2}(\mathrm{mod}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 Modelo:Mvar, módulo un Modelo:Mvar 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 Modelo:Mvar, calcular a inversa e, a continuación, multiplica por Modelo:Mvar para todo Modelo:Math e así conseguir o desexado Modelo:Math.

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

1. Calcular os produtos prefixo $b_i={\prod }_{j=1}^i{a}_j=a_i{b}_{i-1}$ para todo Modelo:Math.
2. Calcula Modelo:Math usando calquera algoritmo coñecido.
3. Para Modelo:Mvar desde Modelo:Mvar ata 2, calcuar
   • Modelo:Math.
   • Modelo:Math.
4. Finalmente, Modelo:Math.

É 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

Modelo:Mvar ≡ 4 (mod 5)

Modelo:Mvar ≡ 4 (mod 7)

Modelo:Mvar ≡ 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

Modelo:Mvar = Modelo:Math (7 × 11) × 4 + Modelo:Math (5 × 11) × 4 + Modelo:Math (5 × 7) × 6

onde

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

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

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

Por tanto,

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

e na súa forma reducida

Modelo:Mvar ≡ 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.

Véxase tamén

Bibliografía

• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro

Outros artigos

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

Ligazóns externas

• Modelo:MathWorld
• Calculadora en liña.