Calcule a^-1 em Zm onde:
a=37 e m=249
Passo 1) Calcule d=mdc(a, m). Se d=1, a e m são
relativamente primos. Então, existe a^-1.
Passo 2) Elabore a equação: a x+m y=1, isto é: a x equiv 1(modm)
Passo 3) Se x for negativo, faça a correção.

Passo 1

Beleza, a gente precisa achar o inverso de 37x equiv 1 pmod249 no anel , ou seja, descobrir um número tal que
Esse assunto é de teoria dos números (aritmética modular) e vamos usar:
  1. o algoritmo de Euclides para calcular o máximo divisor comum (mdc),
  2. o algoritmo de Euclides estendido para escrever esse mdc como combinação linear ,
  3. daí pegar o que resolve essa equação e ajustar (se for negativo) para ficar entre e .

Passo 2

Primeiro confirmamos que 249 &= 6 times 37 + 27, 37 &= 1 times 27 + 10, 27 &= 2 times 10 + 7, 10 &= 1 times 7 + 3, 7 &= 2 times 3 + 1, 3 &= 3 times 1 + 0 , porque se não fosse 1 não existiria inverso.
Aplicando o algoritmo de Euclides:
Como o último resto não nulo é 1, temos . Então o inverso existe.

Passo 3

Agora o Euclides estendido para achar 37x + 249y = 1 e 1 = 7 - 2(10 - 7) = 3cdot7 - 2cdot10 tais que
1 = 3(27 - 2cdot10) - 2cdot10 = 3cdot27 - 8cdot10
Voltando os restos para cima:
  1. 1 = 3cdot27 - 8(37 - 27) = 11cdot27 - 8cdot37 .
  2. Mas 1 = 11(249 - 6cdot37) - 8cdot37 = 11cdot249 - 74cdot37 , então
  1. E , então
  1. E , então
  1. E , então
Logo identificamos e .

Passo 4

Nosso xpositivo = -74 + 249 = 175 resolve , mas ele está negativo. Pra corrigir, adicionamos até ficar num intervalo legal:

Resposta

O inverso de 37 cdot 175 equiv 1 pmod249 em é , pois

Exercícios relacionados