Resolva as seguintes congruências lineares:
20 x equiv 30(bmod 31)

Passo 1

O enunciado pede para resolver a congruência linear
20x equiv 30 pmod31
O conteúdo aqui é teoria de congruências lineares: vamos checar se gcd(20,31) 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:
31 &= 20 cdot 1 + 11, 20 &= 11 cdot 1 + 9, 11 &= 9 cdot 1 + 2, 9 &= 2 cdot 4 + 1, 2 &= 1 cdot 2 + 0
Como o último resto não-nulo é 1, temos gcd(20,31)=1, que de fato divide 30. Logo a congruência tem solução única módulo 31.

Passo 3

Para resolver, precisamos da inversa de 20 em Z31. Fazendo a volta no algoritmo estendido, obtemos
1 = 20cdot14 - 31cdot9,
ou seja, 20cdot14 equiv 1 pmod31. Então 14 é a inversa de 20 módulo 31.

Passo 4

Multiplicamos ambos os lados da congruência original pela inversa de 20:
x equiv 14 cdot 30 pmod31
Agora calculamos 14cdot30 = 420 e reduzimos módulo 31:
420 div 31 = 13 resto 17,
portanto 420 equiv 17 pmod31. Assim
x equiv 17 pmod31

Resposta

x equiv 17 pmod31.

Exercícios de Livros Relacionados