Equações diofantinas pedem soluções inteiras. O segredo não é sair testando casos, mas usar divisibilidade e MDC para descobrir quando existe solução e como descrevê-la.
Forma linear
A diofantina mais importante no início é ax + by = c. Ela aparece em combinações, troco, contagem de passos e problemas de resto.
Equação base
ax + by = c, com x e y inteiros
Critério de existência
A equação ax + by = c tem solução inteira se e somente se mdc(a,b) divide c. Esse é o primeiro teste, sempre.
!
Leitura prática: antes de pensar em resolver, teste se a equação é possível. Muita questão termina aqui.
Exemplo
A equação 12x + 18y = 7 tem solução inteira?
1
mdc(12,18)=6.
2
Como 6 não divide 7, não há solução inteira.
A equação é impossível em inteiros.
Parametrização
Se existe uma solução particular, todas as outras aparecem por deslocamentos controlados. Isso transforma o problema de encontrar várias soluções em um problema de escrever uma família.
Forma geral
Se (x0, y0) resolve ax+by=c, então x = x0 + (b/d)t e y = y0 - (a/d)t
Aqui d = mdc(a,b) e t é inteiro.
Como achar uma solução particular
O jeito mais limpo é usar Bézout. Primeiro resolva ax + by = d, onde d = mdc(a,b). Depois ajuste para c multiplicando tudo por c/d.
Exemplo
Resolva 6x + 9y = 30 em inteiros.
1
Como mdc(6,9)=3 e 3 divide 30, existe solução.
2
Divida tudo por 3: 2x + 3y = 10.
3
Uma solução particular é (x0,y0) = (5,0).
As soluções gerais são x = 5 + 3t e y = -2t, com t inteiro.
Restrições nas soluções
Muitas vezes a questão não quer qualquer inteiro, mas soluções positivas, naturais ou dentro de um intervalo. Depois da parametrização, você transforma isso em desigualdades para t.
É por isso que diofantina não é só conta: ela mistura divisibilidade com leitura de intervalo.
!
Roteiro prático: teste existência, encontre uma solução particular, escreva a família geral e só então imponha positividade, intervalo ou quantidade máxima.
Exemplo com restrição
Encontre as soluções inteiras não negativas de 4x + 6y = 30.
1
Como mdc(4,6)=2 e 2 divide 30, existem soluções inteiras.
2
Divida por 2: 2x + 3y = 15. Uma solução particular é (x0,y0)=(6,1).
3
A família geral é x=6+3t e y=1-2t, com t inteiro.
4
Imponha x ≥ 0 e y ≥ 0: de 6+3t ≥ 0, vem t ≥ -2; de 1-2t ≥ 0, vem t ≤ 0.
Logo t=-2,-1,0, gerando (0,5), (3,3) e (6,1).
Exercício rápido
Cheque rápido
Se ax+by=c tem uma solução particular, o que vem depois para descrever todas as soluções?