Equação diofantina linear: soluções inteiras, moedas e selos
Informe a, b e c da equação a·x + b·y = c: veja o mdc, se há solução inteira, uma solução particular, o passo das demais e quantas soluções têm x e y não negativos (moedas ou selos).
- Roda no seu navegador
Resultado
O resultado aparece aqui.
Como as soluções inteiras são encontradas
a·s + b·t = mdc(a, b) (Euclides estendido); se mdc divide c: x₀ = s·c/mdc, y₀ = t·c/mdc; todas as soluções: x = x₀ + k·b/mdc, y = y₀ − k·a/mdc
O algoritmo de Euclides estendido dá o mdc e os números s e t com a·s + b·t = mdc. Se o mdc divide c, multiplica-se por c/mdc para obter uma solução; as outras andam de b/mdc em x e de a/mdc em y. Com moedas ou selos, interessam as soluções com x e y não negativos.
Exemplo: 3x + 5y = 100
| Passo | Quociente | Resto a | Resto b | s | t |
|---|---|---|---|---|---|
| 1 | 0 | 5 | 3 | 0 | 1 |
| 2 | 1 | 3 | 2 | 1 | 0 |
| 3 | 1 | 2 | 1 | -1 | 1 |
| 4 | 2 | 1 | 0 | 2 | -1 |
Cuidados com soluções inteiras
- A tabela mostra cada passo da divisão de Euclides, com os coeficientes s e t que se carregam de um passo ao outro.
- Sem solução inteira quando c não é múltiplo do mdc; nesse caso os valores de solução saem zerados.
- Soluções não negativas contam os valores de x e y que podem ser usados de verdade (número de moedas ou selos).
- O menor x não negativo e o y correspondente aparecem só quando existe pelo menos uma solução não negativa.
Nota: Resultado exato em inteiros para os valores digitados.
Perguntas frequentes
Como resolver uma equação diofantina linear?
Use Euclides estendido para o mdc: para 3x + 5y = 100 o mdc é 1 e há solução inteira.
Quantas formas de pagar 100 com moedas de 3 e de 5?
São 7 formas com quantidades não negativas de cada moeda.
Quando a equação diofantina não tem solução?
Quando c não é múltiplo do mdc de a e b, como 6x + 9y = 10.