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 .
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
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,
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$ ?
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
RESOLUÇÃO
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;
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
Já conhecia a forma de resolver as equações diofantinas, o que me chamou a atenção foi os casos particulares, me passou despercebido. Com um post muito bem elaborado e escrito, restou pouco para outros blogueiros publicar sobre tal assunto. Parabéns e que continue nos supreendendo com posts interessantes.
ResponderExcluirObrigado, Prof! Na verdade eu sempre achava chato utilizar o algoritmo de Euclides (rs). Uma vez vi um post seu muito interessante sobre as equações do tipo [;x^2+y^2=a;]. Valeu!
ResponderExcluir