Question

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

Answer 1

$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}$