Encontrar todas as soluções de cada uma das seguintes congruências lineares.
(b)
(b)
Passo 1
O enunciado pede para resolver a congruência linear
Isso envolve achar o inverso multiplicativo de
módulo
, pois
é primo e
.
Passo 2
Calculamos
pelo algoritmo de Euclides:
Como o resto não nulo final é
, temos
, logo a inversa de
existe módulo
.
Passo 3
Aplicamos a volta do algoritmo (Euclides estendido) para escrever
como combinação linear:
mas
, então
Isso mostra que
ou seja,
.
Passo 4
Multiplicamos a congruência original por
: