(2,0)Resolva os itens a seguir utilizando o Algoritmo de Euclides ou propriedades de inversos:
(a) Encontre o inverso multiplicativo de [22] módulo 81 .
(b) Resolva a congruência linear:
.
(a) Encontre o inverso multiplicativo de [22] módulo 81 .
(b) Resolva a congruência linear:
Passo 1
O enunciado dá duas tarefas com módulo
:
- (a) Encontrar o inverso multiplicativo de
módulo . - (b) Resolver a congruência linear
.
Informações relevantes fornecidas:
- O número que aparece como coeficiente é
. - O módulo é
. - Na parte (a) pede-se um
tal que em . - Na parte (b) pede-se os
(classe módulo ) que satisfazem a congruência dada.
Passo 2
O que é um inverso multiplicativo em módulo?
- Para um inteiro
e um módulo , um inverso multiplicativo de modulo é uma classe tal que
ou seja,
.
- Importante: um inverso existe se e só se
. Então o primeiro passo prático é calcular usando o Algoritmo de Euclides.
Passo 3
Calcular
com o Algoritmo de Euclides (divisões sucessivas):
A última sobra não-nula é
, logo
Como
, o inverso multiplicativo de
modulo
existe e podemos obtê-lo via o Algoritmo de Euclides estendido (fazendo as substituições para expressar
como combinação linear de
e
).
Passo 4
Executar a volta do Algoritmo de Euclides (substituições) para escrever
como combinação linear de
e
.
Partimos de
Mas
e
vêm das divisões anteriores:
então substituindo:
Agora substituímos
pela expressão obtida da primeira divisão:
portanto
Passo 5
A expressão final mostra
Isto significa que um coeficiente
com
é
. Em termos de classes módulo
,
representa o inverso de
porque
Convertendo
para a classe representativa entre
e
:
Portanto a classe
é um inverso de
módulo
.
Passo 6
Verificação rápida (para ter confiança): calcular
e reduzir módulo
:
Dividindo
por
:
, resta
. Logo
confirmação que
é realmente o inverso de
.
Passo 7
Usar o inverso para resolver a congruência
. Como
é o inverso de
, multiplicamos ambos os lados da congruência por
:
Calcular
. Reduzir
módulo
:
, resto
. Assim a solução (como classe módulo
) é
.
Resposta
(a)
(b)
(b)