Resolva as seguintes congruências lineares:
Passo 1
O enunciado pede para resolver a congruência linear
O conteúdo aqui é teoria de congruências lineares: vamos checar se
divide o termo independente e, como 31 é primo, usar a inversa de 20 no módulo 31.
Passo 2
Calculamos o máximo divisor comum usando o algoritmo de Euclides:
Como o último resto não-nulo é
, temos
, que de fato divide
. Logo a congruência tem solução única módulo
.
Passo 3
Para resolver, precisamos da inversa de
em
. Fazendo a volta no algoritmo estendido, obtemos
ou seja,
. Então
é a inversa de
módulo
.
Passo 4
Multiplicamos ambos os lados da congruência original pela inversa de
:
Agora calculamos
e reduzimos módulo
:
portanto
. Assim