Encontre um inverso de 19 módulo 141.
Passo 1
O enunciado pede um inverso de
no módulo
. Isso significa encontrar um inteiro
tal que
Para isso vamos usar o algoritmo de Euclides estendido, que além de calcular o
também expressa esse
como combinação linear dos números.
Passo 2
Aplicando o algoritmo de Euclides para
e
:
Como o último resto não nulo é
, temos
e o inverso existe.
Passo 3
Agora fazemos a substituição (retro-substituição) para escrever
como combinação linear de
e
.
De
vem
Mas
, então
Como
, substituímos:
E
, daí
Passo 4
A expressão
mostra que
é coeficiente de
na combinação linear, logo