• Matéria: Matemática
  • Autor: Lukyo
  • Perguntado 3 anos atrás

(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.​


Lukyo: você está dizendo que 4n - 5 é múltiplo de 8..
gabrielcguimaraes: E que proveito pode ser tirado disso?
Lukyo: 4n - 5 = 8k ou ainda 4n - 8k = 5, o que é obviamente impossível de resolver
Lukyo: pois o lado esquerdo deve ser múltiplo de mdc(4, 8) = 4. Mas 5 não é múltiplo de 4
gabrielcguimaraes: Interessante
Lukyo: Agora, caso a congruencia fosse 4n ≡ 6 (mod 8)... primeiro a gente simplifica ao maximo a congruencia3
Lukyo: congruência*
Lukyo: simplificando por 2, temos 2n ≡ 3 (mod 4). Também não tem solução
Lukyo: pois mdc(2, 4) = 2, e 3 não é múltiplo de 2
gabrielcguimaraes: Gosto muito das suas aulas. O que eu acho crucial em um professor é que este tenha domínio total e completo do assunto em questão. Mas você não só tem isso, mas tem domínio também de qualquer outro tema que possa vir durante a aula, já para saciar as dúvidas o tão rápido quanto estas surjam. Não sei se você já tem experiência como professor ou recém está iniciando, mas continue assim, suas aulas são excelentes.

Respostas

respondido por: gabrielcguimaraes
2

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}

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:
4q \equiv 1 \pmod {77}\\4q = 77k + 1

Devo, portanto, encontrar um múltiplo de 77 que, somado a 1, resulte em um múltiplo de 4. Como 77 = 76 + 1, 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:

77 \cdot 3 + 1 = 232, múltiplo de 4.

Olhando lá em cima na definição do representante da classe inversa, temos que:

4q = 77k + 1\\4q = 232\\q = 58

Desse modo, basta multiplicar 4 por 58 para isolar a incógnita. Prosseguindo:
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}


gabrielcguimaraes: Recém fiz uma amigável atividade deste mesmo cidadão, caso queira dar uma olhada:
https://brainly.com.br/tarefa/53221581
Congruência modular E algoritmo de Euclides.
Lukyo: Vou verificar. Quanto essa do sistema de duas equações, deixei outra forma de resolução nos comentários lá da tarefa.
gabrielcguimaraes: Sim, já havia visto
gabrielcguimaraes: 3 respostas diferentes.
gabrielcguimaraes: Eu estava vendo, respondi a vigésima questão sua agora
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
gabrielcguimaraes: Sim, claro que é de 97... já arrumei
gabrielcguimaraes: Coloquei isso da existência da classe inversa quase no início da resposta.
Perguntas similares