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 ![\in \mathbb{Z} [;\in \mathbb{Z};]](http://thewe.net/tex/%5Cin%20%5Cmathbb%7BZ%7D)
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)
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 ![mdc(a,b)=1 [;mdc(a,b)=1;]](http://thewe.net/tex/mdc%28a,b%29=1)
Exemplo 4:
tem soluções porque ![mdc(7,10)=1 [;mdc(7,10)=1;]](http://thewe.net/tex/mdc%287,10%29=1)
Exemplo 5:
não tem soluções porque ![mdc(6,15)=3\neq1 [;mdc(6,15)=3\neq1;]](http://thewe.net/tex/mdc%286,15%29=3%5Cneq1)
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 ![c=70 [;c=70;]](http://thewe.net/tex/c=70)
Utilizamos o algoritmo de Euclides para calcular o
:
Logo, o último resto não-nulo é ![d=mdc(91,14)=7 [;d=mdc(91,14)=7;]](http://thewe.net/tex/d=mdc%2891,14%29=7)
Para
temos o equivalente
obtido por intermédio de (*).
Assim,
e
com
e ![c=70 [;c=70;]](http://thewe.net/tex/c=70)
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
onde
Pelas relações
,
e pelo lema acima demonstrado, concluímos que
divide
e
divide
. Logo, existem
e
, tais que
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 ![(x_0,y_0)=\left(\frac{c}{a},0\right) [;(x_0,y_0)=\left(\frac{c}{a},0\right);]](http://thewe.net/tex/%28x_0,y_0%29=%5Cleft%28%5Cfrac%7Bc%7D%7Ba%7D,0%5Cright%29)
. Logo,
2º Caso: Se
é múltiplo de
então ![(x_0,y_0)= \left(\frac{c}{a + b}, \frac{c}{a + b}\right) [;(x_0,y_0)= \left(\frac{c}{a + b}, \frac{c}{a + b}\right);]](http://thewe.net/tex/%28x_0,y_0%29=%20%5Cleft%28%5Cfrac%7Bc%7D%7Ba%20+%20b%7D,%20%5Cfrac%7Bc%7D%7Ba%20+%20b%7D%5Cright%29)
Prova:
![ax+by=(a+b)n \Rightarrow a.\frac{c}{a+b}+ b.\frac{c}{a+b} [;ax+by=(a+b)n \Rightarrow a.\frac{c}{a+b}+ b.\frac{c}{a+b};]](http://thewe.net/tex/ax+by=%28a+b%29n%20%5CRightarrow%20a.%5Cfrac%7Bc%7D%7Ba+b%7D+%20b.%5Cfrac%7Bc%7D%7Ba+b%7D)
![=(a+b).n \Rightarrow [;=(a+b).n \Rightarrow;]](http://thewe.net/tex/=%28a+b%29.n%20%5CRightarrow)
![\frac{c}{a + b}(a + b)=(a+b).n [;\frac{c}{a + b}(a + b)=(a+b).n;]](http://thewe.net/tex/%5Cfrac%7Bc%7D%7Ba%20+%20b%7D%28a%20+%20b%29=%28a+b%29.n)
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 ![(x_0,y_0)= \left(-\frac{c}{|a - b|}, +\frac{c}{|a - b|}\right) [;(x_0,y_0)= \left(-\frac{c}{|a - b|}, +\frac{c}{|a - b|}\right);]](http://thewe.net/tex/%28x_0,y_0%29=%20%5Cleft%28-%5Cfrac%7Bc%7D%7B%7Ca%20-%20b%7C%7D,%20+%5Cfrac%7Bc%7D%7B%7Ca%20-%20b%7C%7D%5Cright%29)
. 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
ingressos de teatro;
ingressos de cinema.
ingressos de teatro;
ingressos de cinema.
ingresso de teatro;
ingressos de cinema.
RESOLUÇÃO
Temos, ainda,
Como
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
:
Para
:
Para
:
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