0009 Famat revista 09 artigo .10

Prévia do material em texto

HEURÍSTICAS E EQUAÇÕES DIOFANTINAS 
 
 
Michelle Crescêncio de Miranda 
Programa Institucional de Iniciação Científica e Monitoria 
 da Faculdade de Matemática – PROMAT 
michellemiranda_18@hotmail.com 
 
 
Luiz Alberto Duran Salomão 
Professor orientador 
salomao@ufu.br 
 
 
Faculdade de Matemática – FAMAT 
Universidade Federal de Uberlândia – UFU 
 
 
Resolver problemas é uma habilidade prática como nadar, esquiar ou 
tocar piano; você pode aprendê-la por meio de imitação e prática. 
(...)se você quer aprender a nadar, você tem que entrar na água e se 
você quer se tornar um bom “resolvedor de problemas”, tem que 
resolver problemas. 
 George Polya 
 
Introdução 
 
Neste artigo, desenvolvemos um breve estudo sobre equações diofantinas. No entanto, não 
menos importante que o tema desenvolvido é a oportunidade de nos exercitarmos em diversas 
heurísticas especialmente adequadas para tratar problemas da natureza que permeia o assunto 
em tela. Uma heurística é uma sugestão ou estratégia geral, independente de algum tópico 
particular ou do assunto em questão, que ajude os “resolvedores de problemas” a abordar e 
entender um problema e a dirigir eficientemente seus recursos para resolvê-lo. Neste breve 
estudo, destacamos o emprego de algumas dessas heurísticas, a saber, a redução de um 
problema a uma situação mais simples, o argumento por contradição, o método da descida 
infinita e o Princípio de Dirichlet. 
 
1. A equação pitagórica 
 
Um dos mais antigos problemas da teoria dos números é a determinação de todas as soluções 
inteiras da equação 
222 zyx =+ . (I) 
Edson
Edson
FAMAT em Revista - Número 09 - Outubro de 2007 181 
Como veremos, a solução dessa equação pode ser obtida através de propriedades elementares 
de números inteiros. 
Um terno (x, y, z) de inteiros que satisfaz (I) é dito um terno pitagórico. Obviamente, vamos 
omitir qualquer caso onde uma das coordenadas do terno (x, y, z) seja zero. Inicialmente, 
notemos que se (x, y, z) é um terno pitagórico, então qualquer terno (kx, ky, kz) também o será, 
onde k é um inteiro diferente de zero. É claro, ainda, que a recíproca da afirmação que 
acabamos de fazer também é verdadeira. Portanto, vamos restringir nossa busca ao caso em 
que as coordenadas x, y, e z do terno não têm nenhum fator comum maior do que 1. Nesse 
caso, dizemos que uma tal solução (x, y, z) de (I) é primitiva. Por exemplo, (3, 4, 5) é uma 
solução primitiva de (I) mas (6, 8, 10), embora seja solução de (I), não é primitiva. Podemos, 
na verdade, dizer que se (x, y, z) é uma solução primitiva de (I) não há duas de suas 
coordenadas que não sejam inteiros primos entre si. Em outras palavras, se (x, y, z) é uma 
solução primitiva de (I), então mdc(x, y) = mdc(x, z) = mdc(y, z) = 1. De fato, se p é um 
número primo divisor comum de x e y, então é claro que p também é divisor de 
e, conseqüentemente de z (pois p é primo), o que contraria o fato de (x, y, z) ser solução 
primitiva de (I). Portanto, mdc (x, y) = 1. Claramente, o mesmo argumento mostra que 
mdc(x,z) = 1 e mdc(y, z) = 1. Como conseqüência do fato que acabamos de justificar, x e y 
não podem ser ambos pares, se (x, y, z) for uma solução primitiva de (I). Porém, podemos 
ainda fazer uma outra afirmação: x e y não podem ser ambos ímpares. De fato, se x = 2a +1 e 
y = 2b+1, onde a, b∈, então x + y = (2a +1) + (2b +1) = 2 + 4( a + a 2 + b + b ), 
ou seja, z é divisível por 2 mas não por 4. Ora, isto não é possível pois, se z é divisível 
por 2, z também o é; daí, z é divisível por 4. Concluímos, assim, que se (x, y, z) é um terno 
pitagórico primitivo, exatamente um dos inteiros x ou y é par e z é ímpar. Vamos assumir 
daqui em diante, sem perda de generalidade, que x é par. 
222 zyx =+
2 2 2 2 2
2 2
2
Vamos, agora, determinar todas as soluções primitivas (x, y, z) de (I), reduzindo o problema a 
uma situação mais simples. Observe que, uma condição necessária para (x, y, z) ser uma 
solução de (I) é que 
x = z - y = (z – y) (z + y). (II). 2 2 2
No caso da solução ser primitiva, z – y e z + y são inteiros pares. Daí, podemos dividir por 4 
os membros extremos de (II), obtendo 
( )( yzyzx −+=⎟⎠
⎞⎜⎝
⎛
4
1
2
1 2 ). 
Edson
Edson
182 FAMAT em Revista - Número 09 - Outubro de 2007
Chamando ( )yzm +=
2
1
1 e ( yzn −= 2
1
1 ), obtemos 
11
2
2
1 nmx =⎟⎠
⎞⎜⎝
⎛ (III) 
e podemos afirmar que e são primos entre si - de fato, se p é um divisor comum de 
e , p divide e p divide 
1m 1n 1m
1n znm =+ 11 ynm =− 11 o que não é possível pois, como vimos, 
mdc(y, z) = 1. Além disso, de (III) concluímos que e são quadrados perfeitos, já que 
mdc = 1 e o produto é um quadrado perfeito. Portanto, existem inteiros positivos 
m e n tais que = m , e = n e mdc(m, n) = 1. Logo, 
1m 1n
( 11, nm ) 11nm
1m
2
1n
2 yzmm
2
1
2
1
1
2 +== , 
yznn
2
1
2
1
1
2 −== e m n =2 2 2
4
1 x . Decorre daí que 
x = 2mn, y = m - n e z = m2 2 +2 n . (IV) 2
 Observe que m e n, em (IV), têm paridades opostas, pois z e y são ímpares. É imediato 
verificar que se x, y, e z são da forma dada em (IV), então (x, y, z) satisfaz a equação 
pitagórica (I). 
As considerações feitas acima permitem-nos enunciar a seguinte proposição.. 
Proposição 1: A condição necessária e suficiente para que (x, y, z) seja um terno pitagórico 
primitivo, com coordenadas positivas, é que existam inteiros positivos m e n, primos entre si, 
de paridades opostas, com m > n, de modo que x = 2mn, y = m - n e z = m + n . 2 2 2 2
A tabela a seguir ilustra parcialmente uma representação dos ternos pitagóricos primitivos, 
conforme a proposição acima. 
 
 
 m 
 
 n 
 
2 
 
 
3 
 
 
 
4 
 
 
5 
 
 
 
6 
 
 
7 
 
 
1 
 
(4,3,5) 
 
(8,15,17) 
 
(12,35,37) 
 
 
2 
 
(12,5,13) 
 
(20,21,29) 
 
(28,45,53) 
 
3 
 
(24,7,25) 
 
 
4 
 
(40,9,41) 
 
(56,33,65) 
 
5 
 
(60,11,61) 
 
 
6 
 
(84,13,85) 
 
 
Edson
Edson
FAMAT em Revista - Número 09 - Outubro de 2007 183 
2. Inexistência de soluções não triviais de algumas equações diofantinas 
 
Ao contrário do que vimos no parágrafo anterior, algumas equações diofantinas podem não 
ter soluções, além das triviais. Uma ferramenta poderosa para provar a inexistência de 
soluções de algumas dessas equações é o método da descida infinita, cuja criação é atribuída 
ao matemático francês Pierre de Fermat (1601 – 1665). Basicamente, esse método consiste em 
supor a existência e uma solução não trivial que seja, em algum sentido, mínima. Em seguida, 
deve-se encontrar uma solução que, de alguma forma, venha a contrariar a minimalidade da 
tal solução, advindo daí uma contradição. A seguir, veremos algumas aplicações desse 
método. 
 
Proposição 2: A equação x2 + y2 =3z2 não tem soluções inteiras não nulas. 
Demonstração: Suponha que a equação dada tenha soluções (x, y, z) em inteiros positivos não 
nulos. Assim, seja (a, b, c) a solução que tenha a coordenada z = c mínima. Sabemos que, se 
um número inteiro n não for múltiplo de 3, então seu quadrado n2 deixa resto 1 quando 
dividido por 3. Daí, a e b têm que ser ambos múltiplos de 3, ou seja, existem inteiros r e s tais 
que a = 3r e b = 3s. Assim, 9r2 + 9s2 =3c2, o que acarreta 3(r2 + s2) = c2. Portanto, c2 é 
múltiplo de 3 e, conseqüentemente, c é múltiplo de 3. Logo, existe um inteirot de modo que 
c=3t. Por fim, temos 3(r2 + s2) =9t2 e, daí, r2 + s2 =3t2, o que quer dizer que o terno (r, s, t) é 
solução da equação dada, com cct <=
3
. Contradição com o fato da coordenada c ser 
mínima. 
 
A proposição a seguir emprega uma pequena variação do método utilizado na Proposição 1. 
 
Proposição 3: A equação x2 + y2 + z2 = 2xyz não tem soluções inteiras não nulas. 
Demonstração: Observe que, no membro da esquerda da equação dada, exatamente um dos 
termos é par ou todos os três são pares. Todavia, na primeira situação, o membro da esquerda 
seria múltiplo de 2 mas não de 4, enquanto o da direita seria múltiplo de 4. Isso reduz o 
problema ao caso em que x, y e z são todos pares. Dessa forma, se (x, y, z) satisfaz a equação 
dada, existem inteiros x1, y1 e z1 tais que x =2x1, y =2y1 e z = 2z1 e, daí, 
 
111
2
1
2
1
2
1 4 zyxzyx =++ . 
Usando o mesmo argumento, temos que existem inteiros x1, y1 e z1 tais que x1 =2x2, y1 =2y2 e 
z1 = 2z2 e, por conseguinte, 
222
2
2
2
2
2
2 8 zyxzyx =++ . 
Este argumento pode ser repetido indefinidamente e, assim, teremos que 
...2...222
...2...222
...2...222
3
3
2
2
1
3
3
2
2
1
3
3
2
2
1
======
======
======
n
n
n
n
n
n
zzzzz
yyyyy
xxxxx
 
o que mostra que x, y e z são divisíveis por 2n, para todo inteiro n. Ora, isso só seria possível 
para x = y = z = 0. 
 
O resultado a seguir é um caso particular do célebre Último Teorema de Fermat. 
 
Proposição 4: A equação diofantina xn + yn = zn não tem soluções em inteiros não nulos, se n 
for um inteiro positivo múltiplo de 4. 
Edson
Edson
184 FAMAT em Revista - Número 09 - Outubro de 2007
Demonstração: Suponha que n = 4k, onde k é um inteiro positivo. Se xn + yn = zn , então 
temos que (xk)4 + (yk)4 = (z2k)2, ou seja, (xk, yk, z2k) será uma solução da equação a4 + b4 = c2. 
Assim, o problema fica reduzido a se mostrar que essa última equação não tem soluções além 
das triviais. Suponha, por absurdo, que a, b e c sejam inteiros positivos que satisfaçam a 
equação a4 + b4 = c2. Além disso, para aplicarmos o método da descida infinita de Fermat, 
vamos incluir a hipótese adicional de que c seja mínima, isto é, que não exista uma outra 
solução (a’, b’, c’), em inteiros positivos, com c’ < c. Então, a e b são primos entre si e, pela 
Proposição 1, existem inteiros positivos primos entre si u e v tais que a2 = u2 – v2, b2 = 2uv 
e c = u2 + v2. Como a2 + v2 = u2, novamente pela Proposição 1, temos que existem inteiros 
positivos primos entre si p e q tais que a = p2 – q2, v = 2pq e u = p2 + q2. Daí, segue que 
b2=2uv = 4pq(p2 + q2). Como p e q são relativamente primos, ambos são também 
relativamente primos com p2 + q2. Agora, sendo 4pq(p2 + q2) um quadrado perfeito, 
deveremos ter p, q e p2 + q2 também quadrados perfeitos; portanto, existem inteiros positivos 
βα , e γ de modo que e . Daí segue que , 
sendo Isso contradiz a minimalidade de c. 
22 , βα == qp 222 γ=+ qp 244 γβα =+
.22222 γγ ≥=+=>+= qpuvuc
 
3. A equação de Pell 
 
Se d é um inteiro positivo que não é um quadrado perfeito, sabemos que d é um número 
irracional. A equação , onde m representa um inteiro qualquer, é conhecida 
como a equação de Pell. É claro que, no caso m=0, a equação de Pell não tem solução além 
da trivial (x = y = 0) pois, caso contrário, teríamos 
mdyx =− 22
y
xd = , o que iria contradizer a 
irracionalidade de d . Neste parágrafo, desenvolveremos um breve estudo sobre a 
determinação das soluções da equação de Pell. 
 
A proposição que veremos a seguir é um resultado clássico devido a P.G. Lejeune Dirichlet 
(1805 – 1859). 
Proposição 5: Dado um número irracional α , existem infinitos racionais 
q
p , com p e q 
inteiros não nulos primos entre si, tais que 2
1
qq
p <−α . 
Demonstração: Dado um inteiro positivo N qualquer, consideremos os N+1 elementos do 
intervalo [0, 1) da forma ⎣ ⎦αα jj − , com Nj ≤≤0 , onde ⎣ ⎦x representa o maior inteiro 
que não supera x. Como [ ) U1
0
1,1,0
−
=
⎟⎠
⎞⎢⎣
⎡ +=
N
k N
k
N
k , pelo Princípio de Dirichlet, existem dois 
desses elementos, digamos ⎣ ⎦αα 11 jj − e ⎣ ⎦αα 22 jj − pertencentes a um mesmo intervalo 
⎟⎠
⎞⎢⎣
⎡ +
N
k
N
k 1, . Supondo, sem perda de generalidade, que j1 < j2 e chamando q = j2 – j1 e 
[ ) [ )αα 12 jjp −= , temos que Npq
10 <−< α e, daí, 211 qqNq
p ≤<−α . Por fim, podemos 
supor que p e q são primos entre si. De fato, se p = p1c e q = q1c, para algum inteiro c>1, 
então 2
1
2
1
1 11
qqq
p <<−α . 
Edson
Edson
FAMAT em Revista - Número 09 - Outubro de 2007 185 
O resultado a seguir mostra a existência de valores de m para os quais a equação de Pell tem 
infinitas soluções nos inteiros. 
 
Proposição 6: Se d é um inteiro positivo que não é um quadrado perfeito, existe um inteiro m 
tal que a equação x2 – dy2 = m admite infinitas soluções inteiras. 
Demonstração: Como d é irracional, segue pela Proposição 5, que existem infinitos pares 
(x, y) de inteiros primos entre si tais que 2
1
y
d
y
x <− (*). Agora, se x e y são inteiros 
satisfazendo essa desigualdade, temos que ( ) 122112122 +<⎟⎟⎠⎞⎜⎜⎝⎛ +<+−<+−=− dydyyydydxyydxydxdyx . 
Segue, daí, que algum inteiro não nulo m entre ( )12 +− d e 12 +d repete-se um número 
infinito de vezes dentre os valores de x2 – dy2, para x e y satisfazendo a condição (*), ou seja, 
a equação x2 – dy2 = m admite infinitas soluções inteiras, para um tal m. 
 
Proposição 7: A equação x2 – dy2 = 1, onde d é um inteiro positivo que não é um quadrado 
perfeito, admite soluções. 
Demonstração: Conforme a Proposição 6, podemos tomar um inteiro não nulo m de modo que 
a equação x2 – dy2 = m admite infinitas soluções inteiras. Podemos escolher duas dessas 
soluções (x1, y1) e (x2, y2) de modo que 21 xx ≠ , mas )(mod21 mxx ≡ e . 
Assim, 
)(mod21 myy ≡
( )( ) ( ) ( ) dyxyxydyxxdyxdyx 211221212211 −+−=−+ . (**) 
Mas, e 2121 ydyxx − ≡ )(mod02121 mdyx ≡− )(mod2112 myxyx ≡ e, daí, existem inteiros u e v 
tais que = mu e 2121 ydyxx − mvyxyx =− 2112 . Segue, então, de (**) que ( )( )dyxdyx 2211 −+ = ( )dvum + e, daí, ( )( )dyxdyx 2211 +− = ( )dvum − . 
Multiplicando, membro a membro, as duas igualdades acima, obtemos ( )( ) ( )222222221212 dvumdyxdyxm −=−−= , ou seja, . 122 =− dvu
Assim, a demonstração estará concluída se mostrarmos que u e v não são nulos. De fato, se u 
= 0, teríamos –dv2 = 1, o que é um absurdo. Se v = 0, teríamos u = 1 ou -1. De (**), viria ( )( )dyxdyx 2211 −+ = e, conseqüentemente, m± ( ) ( )dyxdyx 2211 +±=+ e, ainda, 
21 xx = , o que contraria nossa hipótese sobre as soluções (x1, y1) e (x2, y2). 
 
Proposição 8: Se d é um inteiro positivo que não é um quadrado perfeito então existe uma 
solução (x0, y0) da equação x2 – dy2 = 1, onde x0 e y0 são inteiros positivos, de modo que todas 
as demais soluções (xn, yn) dessa equação satisfazem a condição ( )nnn dyxdyx 00 +=+ , 
para algum inteiro n. 
Demonstração: Mais uma vez, teremos uma aplicação do método da descida infinita. 
Consideremos a solução (x0, y0) da equação dada, com coordenadas inteiras positivas, de 
modo que, dentre todas as soluções da equação, o valor dyx 00 + seja o menor possível. 
Vamos identificar cada solução (x, y) da equação com o número dyx + . Pela igualdade ( )( )dyxdyxdyx +−=− 22 , é fácil ver que o produto de duas soluções da equação 
também é uma solução, no sentido da identificação acima. Vamos mostrar que todas as 
Edson
Edson
186 FAMAT em Revista - Número 09 - Outubro de 2007
soluções da equação dada são da forma ( )ndyx 00 + , para algum inteiro n.Suponha que 
(u, v) seja uma solução da equação em tela e que dvu + não seja uma potência com 
expoente inteiro de dyx 00 + . Assim, para algum n, temos ( )ndyx 00 + < dvu + < ( ) 100 ++ ndyx . 
 Multiplicando cada membro da expressão acima pela solução ( )ndyx 00 − , obtemos 
1 < ( dvu + ) ( )ndyx 00 − < )( 00 dyx + 
o que é um absurdo pois o termo intermediário é uma solução, o que contraria a minimalidade 
da solução dyx 00 + . 
 
Referências bibliográficas 
 
[1] ANDERSON, J. A. e BELL, J. M. – Number Theory with applications – Prentice Hall – 
1997 
[2] ENGEL, A. – Problem-Solving Strategies – Springer – 1997 
[3] MOREIRA, C. G. – Propriedades estatísticas de frações contínuas e aproximações 
diofantinas – Matemática Universitária – Sociedade Brasileira de Matemática – nº 29 – 2000 
[4] MUNIZ NETO, A. C. – Equações Diofantinas – EUREKA! – Sociedade Brasileira de 
Matemática – nº 7 - 2000 
Edson
Edson
FAMAT em Revista - Número 09 - Outubro de 2007 187 
 
Edson
188 FAMAT em Revista - Número 09 - Outubro de 2007
Edson