Encontrar todas as soluções de cada uma das seguintes congruências lineares.
(b) 13 x equiv 14(bmod 29)

Passo 1

O enunciado pede para resolver a congruência linear
13x equiv 14 pmod29
Isso envolve achar o inverso multiplicativo de 13 módulo 29, pois 29 é primo e gcd(13,29)=1.

Passo 2

Calculamos gcd(13,29) pelo algoritmo de Euclides:
29 = 2cdot13 + 3,
13 = 4cdot3 + 1,
3 = 3cdot1 + 0
Como o resto não nulo final é 1, temos gcd(13,29)=1, logo a inversa de 13 existe módulo 29.

Passo 3

Aplicamos a volta do algoritmo (Euclides estendido) para escrever 1 como combinação linear:
1 = 13 - 4cdot3,
mas 3 = 29 - 2cdot13, então
1 = 13 - 4,(29 - 2cdot13) = 9cdot13 - 4cdot29
Isso mostra que
9cdot13 equiv 1 pmod29,
ou seja, ,13^-1equiv9pmod29.

Passo 4

Multiplicamos a congruência original por 13^-1:
x equiv 9cdot14 pmod29
9cdot14 = 126 equiv 126 - 4cdot29 = 126 - 116 = 10 pmod29

Resposta

x equiv 10 pmod29

Exercícios relacionados