Encontre um inverso de 19 módulo 141.

Passo 1

O enunciado pede um inverso de 19 no módulo 141. Isso significa encontrar um inteiro x tal que
19x \equiv 1 \pmod{141}.
Para isso vamos usar o algoritmo de Euclides estendido, que além de calcular o \gcd também expressa esse \gcd como combinação linear dos números.

Passo 2

Aplicando o algoritmo de Euclides para 141 e 19:
141 = 7\cdot19 + 8,
19 = 2\cdot8 + 3,
8 = 2\cdot3 + 2,
3 = 1\cdot2 + 1,
2 = 2\cdot1 + 0.
Como o último resto não nulo é 1, temos \gcd(141,19)=1 e o inverso existe.

Passo 3

Agora fazemos a substituição (retro-substituição) para escrever 1 como combinação linear de 141 e 19.
De
3 = 1\cdot2 + 1
vem
1 = 3 - 1\cdot2.
Mas 2 = 8 - 2\cdot3, então
1 = 3 - 1\,(8 - 2\cdot3) = 3\cdot3 - 8.
Como 3 = 19 - 2\cdot8, substituímos:
1 = (19 - 2\cdot8)\cdot3 - 8 = 3\cdot19 - 7\cdot8.
E 8 = 141 - 7\cdot19, daí
1 = 3\cdot19 - 7\,(141 - 7\cdot19) = 3\cdot19 - 7\cdot141 + 49\cdot19 = 52\cdot19 - 7\cdot141.

Passo 4

A expressão
1 = 52\cdot19 - 7\cdot141
mostra que 52 é coeficiente de 19 na combinação linear, logo
19\cdot52 \equiv 1 \pmod{141}.

Resposta

52

Exercícios de Livros Relacionados