Resolver as seguintes congruencias.
Resolva as seguintes congruências lineares:
Resolva as seguintes congruências lineares:
Passo 1
O enunciado pede para resolver a congruência linear
Aqui o conteúdo é congruências lineares: primeiro verificamos se há solução (checando o
) e depois, se existir, encontramos o inverso modular de
módulo
.
Passo 2
Calculamos o máximo divisor comum de
e
pelo algoritmo de Euclides:
Daí
. Como o
é
,
é invertível módulo
e existe solução única em
.
Passo 3
Usamos o algoritmo estendido para achar inteiros
tais que
Voltando as etapas:
substituindo temos
Logo
, e o inverso de
módulo
é
.
Passo 4
Multiplicamos a congruência original por
:
Conferindo,
, bate com o enunciado.