Flashcard FC627969
Como encontrar o menor número não negativo que satisfaça simultaneamente \(n\equiv a\pmod m\) e \(n\equiv b\pmod k\) quando \(m\) e \(k\) são coprimos?
Conjuntos
NC UFPR (FUNPAR) · 2023
Como encontrar o menor número não negativo que satisfaça simultaneamente \(n\equiv a\pmod m\) e \(n\equiv b\pmod k\) quando \(m\) e \(k\) são coprimos?
Mostrar resposta e comentário
Resposta
Pelo Teorema Chinês dos Restos: existe solução única módulo \(m\cdot k\); escreva \(n=a+mt\) e resolva \(m t\equiv b-a\pmod k\) usando o inverso de \(m\) módulo \(k\).
Procedimento detalhado, passo a passo:
Escreva \(n=a+mt\).
Resolva \(m t\equiv b-a\pmod k\).
Calcule \(m^{-1}\pmod k\), então \(t\equiv (b-a)\,m^{-1}\pmod k\).
Substitua em \(n=a+mt\) e reduza para \(0\le n
Exemplo:
Encontre \(n\) tal que \(n\equiv3\pmod4\) e \(n\equiv2\pmod7\).
\(n=3+4t\).
\(4t\equiv2-3\equiv-1\equiv6\pmod7\).
Como \(4^{-1}\equiv2\pmod7\), temos \(t\equiv6\cdot2\equiv12\equiv5\pmod7\).
Logo \(n=3+4\cdot5=23\), solução mínima \(23\) (módulo \(4\cdot7=28\)).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/625988
Conteúdo do catálogo FC Concursos · Atualizado em