Flashcard FC575230
Como determinar o menor inteiro não negativo k que satisfaça \(k\equiv r_1\pmod{m}\) e \(k\equiv r_2\pmod{n}\)?
Conjuntos
FCC · 2025
Como determinar o menor inteiro não negativo k que satisfaça \(k\equiv r_1\pmod{m}\) e \(k\equiv r_2\pmod{n}\)?
Mostrar resposta e comentário
Resposta
Escreve-se \(k=r_1+m\cdot t\), substitui-se na segunda congruência e resolve-se para \(t\); o menor \(k\ge0\) é o primeiro valor obtido, a solução é única módulo \(\operatorname{lcm}(m,n)\).Explicação, escrever \(k=r_1+m\cdot t\), impor \(r_1+m\cdot t\equiv r_2\pmod{n}\), resolver esta congruência linear em \(t\), obter o menor \(t\ge0\) que gera \(k\ge0\), isto fornece a solução mínima, as demais soluções são obtidas somando múltiplos de \(\operatorname{lcm}(m,n)\).
Exemplo:
Resolver \(k\equiv2\pmod{4}\) e \(k\equiv3\pmod{5}\).
Escreve-se \(k=2+4t\). Substituindo, \(2+4t\equiv3\pmod{5}\), isto é \(4t\equiv1\pmod{5}\).
Como \(4\equiv-1\pmod{5}\), tem-se \(-t\equiv1\pmod{5}\), logo \(t\equiv4\pmod{5}\).
Tomando \(t=4\) obtemos \(k=2+4\cdot4=18\). Assim o menor \(k\ge0\) é \(18\), e as soluções são \(k\equiv18\pmod{20}\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/571940
Conteúdo do catálogo FC Concursos · Atualizado em