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



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  para indicar a clase de congruencia que contén , isto pódese expresar dicindo que o inverso multiplicativo modular da clase de congruencia  é a clase de congruencia  tal que:



onde o símbolo  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



 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

 Terence Tao usa habitualmente a notación sen a palabra "mod", 

Isto é unha relación de equivalencia no conxunto de enteiros, , e as clases de equivalencia chámanse clases de congruencia módulo  ou clases de residuos módulo . Denotamos   como a clase de congruencia que contén o número enteiro ,Úsanse moitas veces outras notacións, incluíndo  e . daquela



Unha congruencia linear é unha congruencia modular da forma



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



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



polo tanto



Se , entón , e  non terá un inverso multiplicativo modular. Polo tanto, {{Math|''b ≡ b (mod m)}} .

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



 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  e  representando as operacións sobre clases de congruencia, estas definicións son



e



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  ou  (conxunto cociente), mais tamén  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, } 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 é , onde  é 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), .

No caso de que  sexa primo, digamos , daquela  e todos os elementos distintos de cero de  teñen inversos multiplicativos, polo tanto  é 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 , sempre acontece que  é o inverso multiplicativo modular de   módulo , xa que . Os exemplos son , , , etc.

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

  xa que 10 divide 32 − 2 = 30, e
  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  ) 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  é un inverso multiplicativo de  módulo .

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  satisfará a congruencia xa que estes enteiros teñen a forma  para algún enteiro  e



é divisíbel por 10. 

O produto das clases de congruencia  e  pódese obter seleccionando un elemento de , digamos 25, e un elemento de , digamos −2, e observando que o seu produto (25)(−2) = −50 está na clase de congruencia . Así, . 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,  .

 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,



Reescrito, isto é



é dicir,



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.Thomas Koshy. Elementary number theory with applications, 2nd edition. . P. 346.

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



onde  é a función total de Euler. Isto débese ao feito de que  pertence ao grupo multiplicativo  × se e só se  é coprimo con . Polo tanto, pódese atopar directamente un inverso multiplicativo modular mediante:



No caso especial onde  é primo,  e o inverso modular vén dada por



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  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.

Categoría:Wikipedia:Páxinas con traducións non revisadas