019-Equação Diofantina Linear

Em complemento aos artigos A combinação linear ax+by e O algoritmo de Euclides, segue este sobre a resolução em da equação diofantina linear

para , , , e , todos

 Conforme já sabemos,

a) é múltiplo inteiro de ; e

b) O algoritmo de Euclides nos permite achar e ainda, e , onde .

Vamos ver como podemos utilizar este conhecimento para resolver a equação em questão.

a) é múltiplo inteiro de .

Temos, então, um critério para saber se a equação tem solução em . A equação terá soluções inteiras, se e somente se, o dividir .

Exemplo 1: Verificar se a equação tem soluções em . Resolução: e divide , logo, existem soluções inteiras para esta equação.

Exemplo 2: Verificar se a equação tem soluções em . Resolução: e não divide , logo, não existem soluções inteiras para esta equação.

Em consequência:

1- Se , a equação sempre terá soluções em . 

Exemplo 3: , com  

2- A equação terá soluções em apenas se

Exemplo 4: tem soluções porque

Exemplo 5: não tem soluções porque

b) O algoritmo de Euclides nos permite achar   e ainda, e , onde  

Com isto, temos uma forma de achar uma solução inicial para , com . De fato, pois sabendo que e , multiplicamos a primeira igualdade de b) por  

 

e assim obtemos a solução inicial e para nossa equação.

Exemplo 6: Vamos achar uma solução inicial para a equação do exemplo 1:

 

Com, , e

Utilizamos o algoritmo de Euclides para calcular o :

  (*)

Logo, o último resto não-nulo é

Para temos o equivalente obtido  por intermédio de (*).

Assim, e com e

 

 

Portanto, a equação possui a solução inicial .

Agora porque solução inicial? Ao contrário da equação que tem um número finito de soluções em , a equação possui infinitas soluções inteiras. Isto deve-se ao fato do caráter aditivo desta equação. As equações diofantinas aditivas e multiplicativas mais simples são, respectivamente, e . No primeiro caso, para qualquer valor temos o correspondente e, portanto, temos infinitas a soluções da forma . No segundo caso, as soluções de são, obviamente, os pares onde e e e, como sabemos, existe um número finito de divisores de . Em , o monômio impõe um caráter multiplicativo a esta equação. Para a equação , diferentemente de , uma inserção aleatória de variável inteira, por exemplo , não garante um correspondente valor inteiro para porque e será inteiro apenas para os múltiplos de . Mas como temos infinitos múltiplos de , temos infinitas soluções para . Existe uma maneira de saber qual é o formato geral das soluções inteiras da equação diofantina linear. Para isto vamos usar o seguinte lema:

Sejam , de forma que . Se for um inteiro, então divide .

Demonstração: implica que existem onde . Decorre que e como divide , por hipótese, vê-se facilmente que divide .

SOLUÇÃO GERAL ( ) DA EQUAÇÃO .

Seja uma solução inicial e uma outra solução. Assim,

 

Dividindo ambos os membros por , temos

(1) ,

 onde  

Pelas relações  , e pelo lema acima demonstrado, concluímos que divide e divide . Logo, existem e , tais que

(2)

(3)

Agora vamos provar que . Para isso, basta substituir (2) e (3) em (1):

 

 

Sendo e lembrando que e concluímos que a solução geral em da equação diofantina linear é ( ver (2) e (3) ):

,

com

ATALHOS PARA UMA SOLUÇÃO INICIAL

O algoritmo de Euclides nos permite, de modo geral, achar uma solução inicial para .Mas, dependendo dos valores de , e podemos ter uma maneira rápida de conseguir . Temos três casos básicos:

1º Caso: Se é múltiplo de ou então ou , respectivamente.

Prova: 1)  ,  

            2)  ,

Exemplo 7: Resolver em a equação . Resolução: a equação tem solução pois  divide . Como é múltiplo de , temos .  Logo,

 

 

2º Caso: Se é múltiplo de então

Prova:
 

Exemplo 8: Resolver em a equação . Resolução: a equação tem solução pois divide . Como  é múltiplo de , temos. Assim,

 

  

3º Caso: Se é múltiplo de então , se e , se .

Prova: análoga ao do 2º caso para cada desigualdade.

Exemplo 9: Resolver em a equação . Resolução: é múltiplo de o que diz que a equação tem solução. Como é múltiplo de e , temos . Portanto,

  

EXEMPLO 10

Valdir, com R$ no bolso, deseja comprar ingressos de teatro e de cinema que estão em promoção, para fins de sorteio em uma festa. Sabendo que o ingresso do teatro custa R$ e o do cinema custa  R$ , de quantas formas possíveis Valdir pode comprar ingressos de teatro e cinema com R$ ?

RESOLUÇÃO

A questão equivale a resolver a equação diofantina , sendo a quantidade de ingressos de teatro e a quantidade de ingressos de cinema. Temos, então, , e .


Temos, ainda, que, sendo divisor de , nos garante que a equação tem solução em . No entanto, procuramos soluções positivas e verificaremos sua existência analisando as soluções gerais.

Como é múltiplo de , uma primeira solução em seria ( conforme o 1º caso de atalho para obter uma solução inicial ).As outras soluções inteiras são representadas por

 

 

Para obter soluções positivas temos que ter e e isto equivale à e . Mas como é natural, temos . Logo, para , e , as condições do problema de Valdir são satisfeitas. Então ele possui modos de comprar ingressos de teatro e cinema com R$ naquelas condições de preço:

Para :

ingressos de teatro;

ingressos de cinema.

Para :

ingressos de teatro;

ingressos de cinema.

Para :

ingresso de teatro;

ingressos de cinema.

E assim, Valdir fica satisfeito de poder escolher a alternativa que mais lhe convier.



REFERÊNCIA BIBLIOGRÁFICA

- Teoria dos Números, de  Salahoddin Shokranian, Marcus Soares, Hemar Godinho; Editora UNB, 1998;

- O que é a Matemática?, de Richard Courant e Herbert Robbins, Editora Moderna, 2000.

Imagem: http://www.overmundo.com.br/overblog/do-pio-de-ave-ao-piano-de-nazareth