Flashcard FC575447
Como usar congruências para encontrar valores inteiros não negativos que resolvem uma equação linear diofantina ax+by=c?
Proporcionalidade
FCC · 2025
Como usar congruências para encontrar valores inteiros não negativos que resolvem uma equação linear diofantina ax+by=c?
Mostrar resposta e comentário
Resposta
Reduza a equação módulo de um dos coeficientes para obter uma congruência que determina uma variável, escolha a menor solução inteira não negativa e calcule a outra variável, verificando divisibilidade e não negatividade.Exemplo: Resolver \(7x+4y=53\) em inteiros não negativos.
Aplicar congruência módulo 4: \(7x\equiv53\pmod4\). Como \(7\equiv3\), temos \(3x\equiv1\pmod4\).
A inversa de 3 em módulo 4 é 3, então \(x\equiv3\pmod4\). A menor solução não negativa é \(x=3\).
Calcule \(y\): \(y=\dfrac{53-7\cdot3}{4}=\dfrac{53-21}{4}=\dfrac{32}{4}=8\).
Verificação: \(7\cdot3+4\cdot8=21+32=53\).
Solução geral: \(x=3+4t,\;y=8-7t\) com \(t\) inteiro, para não negativos \(t=0\) ou \(t=1\), dando \((x,y)=(3,8)\) e \((7,1)\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/572157
Conteúdo do catálogo FC Concursos · Atualizado em