Equações Diofantinas

EQUAÇÕES DIOFANTINAS LINEARES

Imagine que você e mais dois amigos decidem comprar um pacote de biscoito que custa R$ 3,25, no armarinho. Todos juntos só possuem moedas de R$ 1,00 e de R$ 0,25. Então, aparece a pergunta:

de quantas formas diferentes podemos pagar esse biscoito utilizandosomente as moedas de R$ 1,00 e de R$ 0,25?

Podemos montar a equação 1.x + 0,25.y = 3,25 ou multiplicarmo-la toda por 100, o que nos dará 100x + 25y = 325. Repare que não se trata de um sistema linear, pois temos somente 1 equação e 2 incógnitas. Logo, queremos determinar todos os pares (x, y), inteiros, que satisfaçam a equação.

Neste caso, particularmente, x e y devem ser números naturais, pois representam as quantidades de moedas de R$ 1,00 e de R$ 0,25; assim só podem ser positivos. Contudo, inicialmente, resolveremos de maneira geral.

Temos de isolar uma das incógnitas; nesse exemplo, é interessante isolar o x, pois o 100 será o denominador e, dessa forma, é bem simples determinar a condição para que tenhamos uma divisão exata por 100.

− + = ⇒ = − ⇒= 325 25y 100x 25y 325 100x 325 25y x 100 , assim vamos verificar qual a condição que y deve obedecer para que 325 25y − 100 seja um número inteiro. Trabalhando o numerador da fração:

temos − +− − − = = + =+ 325 25y 300 25 25y 300 25 25y 25(1 y) 3 100 100 100 100 100 .
Assim, para que a divisão seja exata, temos que (1 – y) deve ser múltiplo de 4, assim: (1 – y) = 4k ⇒ y = 1 – 4k.
Enfim, podemos ter uma solução geral:y 1 4k 25(4k) x 3 3k 100 e visualizar todas soluções inteiras na tabela.

Algumas soluções estão expressas na tabela, mas, dentro do conjunto dos números inteiros, elas são in nitas, então podemos dar a solução geral (3 + k, 1 – 4k) com k ∈ .

Entretanto, em questões que retratam uma situação real que, por ventura, não aceitem soluções negativas, podemos restringir antes:

− ≥⇒ ≥⇒ ≤ 325 25y x 0 0 25y 325 100 . Mas, como há também y ≥ 0, teremos 0 25y 325 0 y 13 ≤ ≤ ⇒≤≤ . Daí − = + 25(1 y) x 3 100 , temos que (1 – y) seja múltiplo de 4, fazendo com que y seja um número congruente a 1 no (mod 4) entre 0 e 13, por m: y = 1, y = 5, y = 9 ou y = 13. Assim:
y1 x3
y5 x2
y9 x1
y 13 x 0

que são todas as soluções naturais da equação. Portanto, você e seus amigos podem pagar o biscoito de 4 maneiras diferentes.

SOLUÇÃO DE AX + BY = C

A equação diofantina linear ax + by = c possui solução se, e somente se, o máximo divisor comum de a e b dividir c.
A solução particular é (x0 , y0 ) e o restante das soluções são:

b a x x t e y y t d d , com t ∈ , em que d = mdc (a, b).

Encontraremos a solução da equação ao utilizar o máximo divisor comum pelo método de Euclides.
Exemplo:
Encontrar uma solução particular de 18x + 5y = 48. Como mdc (18, 5) = 1 e 1|48, a equação tem solução. Utilizando
o algoritmo de Euclides para a determinação do mdc:

3 1 1 2
18 5 3 2 1
3 2 1 0

Escrevendo as equações a partir do algoritmo e isolando os restos,
teremos:

= +⇒= −
= +⇒=−
= +⇒= −
= +
18 5.3 3 3 18 5.3
5 3.1 2 2 5 3.1
3 2.1 1 1 3 2.1
2 1.2 0

1 3 2.1 1 3 (5 3).1 1 3 5 3 1 2.3 5
1 2(18 5.3) 5 1 18.2 5.6 5 1 18.2 5.7 18.2 5.( 7) 1
Multiplicando toda a equação por 48, teremos 18.96 + 5.(-336) = 48, logo x = 96 e y = – 336.

Se quisermos todas as soluções, teremos x = 96 + 5t e y = -336 – 18t. Se quisermos s soluções inteiras e positivas, teremos x > 0 e y > 0, assim:

96 5t 0 t 19,2 x 96 5.( 19) 1 t 19
336 18t 0 t 18,66 y 336 18( 19) 6
Seja ax + by = c, com mdc (a,b) = 1 e a, b ∈ *. O maior inteiro c para o qual não há soluções inteiras não negativas é ab – a – b.

FUNÇÃO MAIOR INTEIRO (OU FUNÇÃO PISO)

Função maior inteiro (ou função piso) é a função que associa a cada número real x o maior inteiro menor ou igual a x, e denota-se por x . Assim, x é o único inteiro que satisfaz x 1 x x. −< ≤   xx x = +   { }, em que 0x1 ≤ < { } é a parte fracionária de x.

Exemplo:

2 2, 2,1 2, 2,1 3.  = = − =−      
Note que x x  = se, e somente se, x é inteiro.
Vale também a desigualdade    +≥ +      x y x y.
Em uma divisão de dividendo D, divisor d, quociente q e resto r,
valeDq.