(Aritmética: sistema linear de congruências modulares)
Seja N um numero natural que deixa resto 4 na divisão por 7, e que deixa resto 7 na divisão por 11.
Calcule o resto da divisão de N por 77.
─────
Obs.: O uso de sistema linear de congruências e/ou Teorema Chinês dos Restos NÃO É obrigatório para resolver esta tarefa, é apenas uma das diversas formas de resolução. Escolha livremente aquela que julgar mais conveniente.
Para isolar n, basta multiplicar 4 por algum representante da classe inversa de 4, mod 77, já que este produto resultará em 1, por definição. Chamando de q este representante, temos que: [tex]4q \equiv 1 \pmod {77}\\4q = 77k + 1[/tex]
Devo, portanto, encontrar um múltiplo de 77 que, somado a 1, resulte em um múltiplo de 4. Como [tex]77 = 76 + 1[/tex], e 76 é múltiplo de 4, temos que, ao ir multiplicando o 77 (de 1 para cima, tentando achar o valor de k), acharemos em, no máximo 4 multiplicações, um múltiplo de 77 que somado a 1 seja um múltiplo de 4. Justamente em conta disto, podemos encontrar o valor de k por tentativa e erro. Desse modo encontramos o 3, já que:
[tex]77 \cdot 3 + 1 = 232[/tex], múltiplo de 4.
Olhando lá em cima na definição do representante da classe inversa, temos que:
[tex]4q = 77k + 1\\4q = 232\\q = 58[/tex]
Desse modo, basta multiplicar 4 por 58 para isolar a incógnita. Prosseguindo: [tex]4n \equiv -5 \pmod {77}\\58(4n) \equiv 58 \cdot (-5) \pmod {77}\\232n \equiv -290 \pmod {77}\\77 \cdot 3n + n \equiv -290 + 77\cdot 4\pmod {77}\\n \equiv 18 \pmod {77}[/tex]
3 votes Thanks 2
gabrielcguimaraes
Tenho que ir, quando voltar vejo se posso responder alguma outra questão. Tchau.
Lukyo
Beleza, depois veja lá no final da sua resposta.. "então este é um representante da classe inversa de 19, mod 307." creio que seria classe inversa do 97, mod 307.,
Lukyo
Apenas reforce que só é possível encontrar tal classe inversa pois mdc(97, 307) = 1
Lista de comentários
Verified answer
[tex]n \equiv 4 \pmod {7}\\11n \equiv 44 \pmod {77}\\\\n \equiv 7 \pmod {11}\\7n \equiv 49 \pmod {77}\\7n - 5 \equiv 44 \pmod {77}\\\\11n \equiv 7n - 5 \pmod {77}\\4n \equiv -5 \pmod {77}[/tex]
Para isolar n, basta multiplicar 4 por algum representante da classe inversa de 4, mod 77, já que este produto resultará em 1, por definição. Chamando de q este representante, temos que:
[tex]4q \equiv 1 \pmod {77}\\4q = 77k + 1[/tex]
Devo, portanto, encontrar um múltiplo de 77 que, somado a 1, resulte em um múltiplo de 4. Como [tex]77 = 76 + 1[/tex], e 76 é múltiplo de 4, temos que, ao ir multiplicando o 77 (de 1 para cima, tentando achar o valor de k), acharemos em, no máximo 4 multiplicações, um múltiplo de 77 que somado a 1 seja um múltiplo de 4. Justamente em conta disto, podemos encontrar o valor de k por tentativa e erro. Desse modo encontramos o 3, já que:
[tex]77 \cdot 3 + 1 = 232[/tex], múltiplo de 4.
Olhando lá em cima na definição do representante da classe inversa, temos que:
[tex]4q = 77k + 1\\4q = 232\\q = 58[/tex]
Desse modo, basta multiplicar 4 por 58 para isolar a incógnita. Prosseguindo:
[tex]4n \equiv -5 \pmod {77}\\58(4n) \equiv 58 \cdot (-5) \pmod {77}\\232n \equiv -290 \pmod {77}\\77 \cdot 3n + n \equiv -290 + 77\cdot 4\pmod {77}\\n \equiv 18 \pmod {77}[/tex]