Resolva os itens a seguir utilizando o Algoritmo de Euclides ou propriedades de inversos:
(a) Encontre o inverso multiplicativo de [17] módulo 64.
(b) Resolva a congruência linear:
.
(a) Encontre o inverso multiplicativo de [17] módulo 64.
(b) Resolva a congruência linear:
Passo 1
O enunciado pede duas coisas:
- (a) Encontrar o inverso multiplicativo de
no anel , ou seja, encontrar uma classe tal que
- (b) Resolver a congruência linear
isto é, encontrar todas as classes de
módulo
que satisfazem a congruência.
Informações relevantes dadas pelo enunciado:
- O módulo é
. - O coeficiente multiplicador é
. - O termo do lado direito da congruência no item (b) é
.
Passo 2
Conceitos úteis e plano (explicação didática):
- Um número
tem inverso multiplicativo módulo se e só se . Se a for , existe tais que
pela identidade de Bézout. Reduzindo essa igualdade módulo
obtemos
, ou seja,
é o inverso de
em
.
- O Algoritmo de Euclides estendido permite calcular esses
e encontrando a e, no processo de retro-substituição, os coeficientes de Bézout. - Se o inverso de
existir, a solução da congruência é única modulo e dada por
Vou aplicar o Algoritmo de Euclides para
e depois obter os coeficientes de Bézout.
Passo 3
Aplicando o Algoritmo de Euclides (mostrando cada divisão com resto):
Como o último resto não nulo é
, temos
. Portanto o inverso de
módulo
existe.
Passo 4
Agora encontramos os coeficientes de Bézout por retro-substituição (mostrar passo a passo):
Partimos de
Partimos de
Substituímos
pela expressão obtida na segunda linha:
então
Agora substituímos
pela expressão da primeira linha:
portanto
Desenvolvendo:
Assim obtemos a identidade de Bézout
Reduzindo módulo
dá
logo
é um inverso de
módulo
.
Passo 5
Passamos para representante positivo do inverso:
. Portanto
Fazendo a checagem rápida:
e
, confirmando o resto
.
Logo o inverso multiplicativo de
em
é
.
Passo 6
Resolver a congruência
.
Como já temos
, multiplicamos ambos os lados da congruência por
:
Calculamos
. Agora reduzimos módulo
:
portanto
. Assim
Observação didática: como
, a solução é única na classe dos resíduos módulo
; todas as soluções inteiras são
com
.
Resposta
(a)
(b)