Resolva os seguintes sistemas de conguências lineares com três ECL, caaso tenha solução, aplicando o teorema chinês do resto sempre que for possível:
Passo 1
Beleza, o enunciado pede para resolver este sistema de congruências lineares usando o Teorema Chinês do Resto (CRT):
Conteúdo: sistemas de congruências e o CRT.
O que vamos precisar:
O que vamos precisar:
- confirmar que os módulos (29, 31, 11) são coprimos;
- calcular o produto total
e os “pedacinhos” ; - achar inversos de cada
módulo (usando Euclides Estendido); - somar tudo e reduzir módulo
.
Passo 2
Primeiro, 29, 31 e 11 são primos entre si (cada par não tem fator comum além de 1), então o CRT vale. Definimos:
Passo 3
Calcula-se o produto total
Agora cada pedaço
$$M_1=\frac{M}{m_1}=\frac{9889}{29}=341,\quad
M_2=\frac{9889}{31}=319,\quad
M_3=\frac{9889}{11}=899.$$
Passo 4
Precisamos do inverso de cada
Mi,yiequiv1pmodmi módulo
, ou seja
tal que
Usando o Algoritmo de Euclides Estendido:
1) 341 mod 29 = 22 → inverter 22 mod 29:
– 29 = 1·22 +7
– 22 = 3·7 +1
Voltando, acha-se
2) 319 mod 31 = 9 → inverter 9 mod 31:
– 31=3·9+4
– 9=2·4+1
Dá
3) 899 mod 11 = 8 → inverter 8 mod 11:
– 11=1·8+3
– 8=2·3+2
– 3=1·2+1
Chega em
Passo 5
Agora montamos a solução pelo CRT:
Calculando cada termo:
soma total
168112 bmod 9889 = 168112 - 17cdot9889 = -1 equiv 9888pmod9889 . Agora reduzimos módulo
: