Equações de Pell

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:

x^2 + y^2 = z^2

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 x^n + y^n = z^n com n > 2, 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, x e y, da forma

ax + by = c

Onde a, b, c são constantes inteiras. No caso em que c é o máximo divisor comum de a, b, temos a identidade de Bézout. É possível encontrar um par x, y inteiro usando o algoritmo de Euclides estendido.

Note entretanto que há infinitas soluções inteiras para essa equação, pois se x, y é uma solução, x' = x + b e y' = y - a é 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) x^2 - ny^2 = 1

Onde n é um inteiro positivo. Se n não possui raíz exata, então existem infinitas soluções inteiras x, y (Se n tiver raíz exata dá pra mostrar que a única solução é x = \pm 1 e y = 0). Vamos apresentar um algoritmo para encontrar as soluções para esse caso particular de n.

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 d, os coeficientes de sua fração continuada, a_0, a_1, \cdots, a_n são positivos e podem ser calculados através das recorrências, para i \ge 1:

r_i = \frac{1}{r_{i-1} - a_{i-1}}

a_i = \lfloor r_i \rfloor

e com a_0 = \lfloor d \rfloor.

Podemos representar uma fração continuada por seus coeficientes, ou seja, [a_0,a_1,a_2,\cdots]. Incrivelmente, no caso particular em que o número irracional é da forma \sqrt{n}, prova-se que os coeficientes da sua fração continuada são periódicos, ou seja \sqrt{n} = [a_0, \overline{a_1,a_2,\cdots,a_{r-1},a_{r}}] e a_{r} = 2a_0.

Como um exemplo, para n = 14 temos \sqrt{14} = [3,\overline{1,2,1,6}]

É possível calcular explicitamente o numerador p_i e o denominador q_i da fração continuada com i termos, através das recorrências:

\begin{array}{lcl}   p_0 & = & a_0\\  p_1 & = & a_1 a_0 + 1\\  p_n & = & a_n p_{n-1} + p_{n-2}   \end{array}

e

\begin{array}{lcl}   q_0 & = & 1\\  q_1 & = & a_1\\  q_n & = & a_n q_{n-1} + q_{n-2}   \end{array}

A fração p_i / q_i é chamada de n-ésimo convergente. Voltando ao exemplo para n = 14, temos:

\begin{array}{llcl}   i: & p_i / q_i  &  & \\  0:  & 3/1 & = & 3.0\\  1: & 4/1 & = & 4.0\\  2: & 11/3 & = & 3.66666666667\\   3: & 15/4 & = & 3.75\\  4: & 101/27 & = & 3.74074074074  \end{array}

Sendo que \sqrt{14} é aproximadamente 3.74165769645

Uma solução para a equação de Pell

Considere os coeficientes da fração continuada de \sqrt{n} e r o índice a partir do qual os coeficientes ficam periódicos.

Se r é par, seja x = p_{r-1} e y = q_{r-1}. Caso contrário, seja x = p_{2r-1} e y = q_{2r-1}. Surpreendentemente, existe um teorema que diz que x, y 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 p_i e q_i, até encontrar r tal que a_r = 2a_0. Segundo Lenstra [2], r \in O(\sqrt{n} \log n), ou seja, tem complexidade pseudo-polinomial. Assim, se d é o número de bits necessários para representar n, temos que r \in O(2^{d/2}d), 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 (x_1,y_1), Lenstra [2] afirma que se ordenarmos as soluções por magnitude, então a k-ésima solução (x_k, y_k) é tal que

(2) x_k + \sqrt{n}y_k = (x_1 + \sqrt{n}y_1)^k

Usando a ideia de [1], como ambos (x_1,y_1) e (x_k, y_k) são solução para (1), temos

x_k^2 - ny_k^2 = (x_1^2 - ny_1^2)^k = 1

Fatorando temos,

(x_k + \sqrt{n}y_k)(x_k - \sqrt{n}y_k) = (x_1 + \sqrt{n}y_1)^k(x_1 - \sqrt{n}y_1)^k

Por (2), concluímos que,

(3) x_k - \sqrt{n}y_k = (x_1 - \sqrt{n}y_1)^k

Resolvendo para (2) e (3), chegamos em:

\begin{array}{lcl}   x_k & = & \dfrac{(x_1 + y_1\sqrt{n})^k + (x_1 - y_1\sqrt{n})^k}{2}\\  \\  y_k & = & \dfrac{(x_1 + y_1\sqrt{n})^k - (x_1 - y_1\sqrt{n})^k}{2\sqrt{n}}  \end{array}

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

Uma resposta a Equações de Pell

  1. leonardo diz:

    sera que não teria um videoa com a aula sobre pell

%d bloggers like this: