Resolva as congruências lineares:
.
Passo 1
Beleza, o enunciado é: “Resolva a congruência
Isso faz parte de congruências lineares (modular arithmetic). Para resolver precisamos:
- Verificar se existe solução (checar o máximo divisor comum, m.d.c.)
- Se existir, achar o inverso de 25 módulo 29 (usando o Algoritmo de Euclides Estendido)
- Multiplicar ambos os lados pelo inverso encontrado
Passo 2
Primeiro a gente vê se a equação tem solução. A regra diz que a congruência
tem solução sse
divide
. Aqui
,
e
.
Calculemos com o Algoritmo de Euclides:
29 = 25·1 + 4
25 = 4·6 + 1
4 = 1·4 + 0
Logo .
Como 1 divide 15, existe solução única módulo 29.
Calculemos
29 = 25·1 + 4
25 = 4·6 + 1
4 = 1·4 + 0
Logo
Como 1 divide 15, existe solução única módulo 29.
Passo 3
Com
sabemos que 25 tem inverso em
. Vamos achar esse inverso via Euclides Estendido:
1 = 25 − 4·6
e como 4 = 29 − 25·1, substituímos:
1 = 25 − 6(29 − 25) = 25·7 − 29·6.
Isso mostra que
1 = 25 − 4·6
e como 4 = 29 − 25·1, substituímos:
1 = 25 − 6(29 − 25) = 25·7 − 29·6.
Isso mostra que
ou seja, o inverso de 25 modulo 29 é 7.
Passo 4
Agora multiplica a congruência original por 7 dos dois lados:
Basta reduzir
módulo 29:
, então
.