Equações diofantinas são equações polinomiais que só admitem soluções inteiras. Neste post, vou comentar sobre três casos particulares e me concentrar em um deles, conhecido como equações de Pell.
Triplas de Pitágoras
O caso mais conhecido de equações diofantinas é da forma:
As soluções inteiras para essa equação são conhecidas como triplas pitagóricas, por causa do teorema de Pitágoras, sobre a relação entre os comprimentos dos lados de um triângulo retângulo.
Para o caso mais geral, da forma com
, o famoso último teorema de Fermat diz que não existem soluções inteiras.
Indentidade de Bézout
Outro caso particular conhecido são as equações diofantinas lineares de duas variáveis, por exemplo, e
, da forma
Onde são constantes inteiras. No caso em que
é o máximo divisor comum de
, temos a identidade de Bézout. É possível encontrar um par
inteiro usando o algoritmo de Euclides estendido.
Note entretanto que há infinitas soluções inteiras para essa equação, pois se é uma solução,
e
é também uma solução.
Equação de Pell
Só recentemente ouvi falar sobre um outro caso particular, conhecido como equações de Pell, com a forma:
(1)
Onde é um inteiro positivo. Se
não possui raíz exata, então existem infinitas soluções inteiras
(Se
tiver raíz exata dá pra mostrar que a única solução é
e
). Vamos apresentar um algoritmo para encontrar as soluções para esse caso particular de
.
Frações continuadas
Um conceito usado no algoritmo é o de frações continuadas, que podem ser usadas para aproximar um número irracional através de frações. A fração continuada possui a seguinte forma:
Dado um número , os coeficientes de sua fração continuada,
são positivos e podem ser calculados através das recorrências, para
:
e com .
Podemos representar uma fração continuada por seus coeficientes, ou seja, . Incrivelmente, no caso particular em que o número irracional é da forma
, prova-se que os coeficientes da sua fração continuada são periódicos, ou seja
e
.
Como um exemplo, para temos
É possível calcular explicitamente o numerador e o denominador
da fração continuada com
termos, através das recorrências:
e
A fração é chamada de n-ésimo convergente. Voltando ao exemplo para
, temos:
Sendo que é aproximadamente
Uma solução para a equação de Pell
Considere os coeficientes da fração continuada de e
o índice a partir do qual os coeficientes ficam periódicos.
Se é par, seja
e
. Caso contrário, seja
e
. Surpreendentemente, existe um teorema que diz que
representam a menor solução inteira positiva para (1).
Algoritmo
Dadas essas propriedades, um algoritmo para encontrar uma solução para (1), consiste em iterar sobre os coeficientes e
, até encontrar
tal que
. Segundo Lenstra [2],
, ou seja, tem complexidade pseudo-polinomial. Assim, se
é o número de bits necessários para representar
, temos que
, ou seja, mesmo ignorando as complexidades das operações artiméticas no código, o nosso algoritmo é exponencial no número de bits.
Gerando mais soluções
Dada uma solução fundamental , Lenstra [2] afirma que se ordenarmos as soluções por magnitude, então a k-ésima solução
é tal que
(2)
Usando a ideia de [1], como ambos e
são solução para (1), temos
Fatorando temos,
Por (2), concluímos que,
(3)
Resolvendo para (2) e (3), chegamos em:
Implementação
Com base na teoria apresentada acima, é simples escrever um algoritmo. Adicionei uma implementação em python à minha biblioteca pessoal de teoria dos números, disponível no github.
Encontrei um post bastante interessante sobre equações de Pell e Haskell aqui [3]. Para praticar, resolvi implementar a minha versão antes de olhar o código do post. Apanhei bastante para lidar com o fato do Haskell não fazer conversão de tipos ponto flutuante e inteiro automaticamente. É preciso fazer isso explicitamente e por isso a função fromIntegral
no código deste link.
Leitura complementar
[1] Wolfram – Pell Equation
[2] Solving the Pell Equation – H. W. Lenstra Jr.
[3] A Foray into Number Theory with Haskell