Teoria de números/Equações diofantinas

Neste capítulo serão estudados certos problemas cuja solução envolve conceitos da teoria de números que foram tratados nos capítulos anteriores.

Considere o seguinte problema:

Se existem notas de 2 e de 5 reais, quais são os valores que podem ser obtidos combinando algumas dessas notas?

Matematicamente, o que se quer saber é:

Quais os valores de $n\,\!$, para os quais a solução $2x+5y = n\,\!$ possui alguma solução inteira?

Em geral, as equações que surgem no contexto da teoria de números devem ser resolvidas no conjunto dos números inteiros. Este tipo de equação é conhecido como equação diofantina.

As equações diofantinas lineares

A equação que surgiu do exemplo apresentado no início do capítulo é apenas um caso particular da seguinte: $ax+by = n\,\!$. Aqui, os inteiros $a\,\!$ e $b\,\!$ são fixados.

Quando é que tal equação possui solução?

O próximo teorema responde exatamente essa pergunta.

Teorema

Dados $a,b \in \mathbb{Z}\,\!$, existem $x,y \in \mathbb{Z}\,\!$ tais que $ax+by = n\,\!$ se, e somente se, $d = (a,b)|n\,\!$. Além disso, se $(x_0,y_0)\,\!$ é solução, então todas as soluções são da forma: $x = x_0 - b't\,\!$ e $y = y_0 +a't\,\!$, onde $a=a'd\,\!$ e $b=b'd\,\!$.

Demonstração

Primeiramente, observe que se $(x,y)\,\!$ é uma solução, então $d|ax+by = n\,\!$ (pela linearidade da divisibilidade). Reciprocamente, se $d|n\,\!$, então $n=n'd\,\!$. Mas pelo teorema de Bézout, existem inteiros $r,s\,\!$ tais que $ar+bs=d\,\!$. Logo, multiplicando cada membro por $n'\,\!$, tem-se: $n'(ar+bs)=n'd=n\,\!$ ou seja, basta tomar $x=n'r\,\!$ e $y=n's\,\!$, e $(x,y)\,\!$ será uma solução. Resta determinar a forma geral de todas as soluções. Se $(x_0,y_0)\,\!$ for uma solução conhecida, qualquer outra solução $(x,y)\,\!$ satizfaz: $n = ax+by=ax_0+by_0\,\!$ Então $a(x-x_0)+b(y-y_0)=0\,\!$, ou seja, $a(x-x_0)=-b(y-y_0)\,\!$. Tomando $d=(a,b)\,\!$ é possível escrever $a=a'd\,\!$ $b=b'd\,\!$ Donde: $a'(x-x_0)=-b'(y-y_0)\,\!$ Claramente $(a',b')=1\,\!$ e $a'|-b'(y-y_0)\,\!$. Logo $a'|(y-y_0)\,\!$ ou seja, existe $t \in \mathbb{Z}\,\!$ tal que $a't=y-y_0\,\!$ Portanto, $y=y_0+a't\,\!$ Usando essa expressão em $a'(x-x_0) = -b'(y-y_0)\,\!$ resulta $a'(x-x_0) = -b'(y_0+a't-y_0) = -b'a't\,\!$ Disto se conclui que $x=x_0-b't\,\!$.

Assim como acontece em problemas que envolvem equações diferenciais, para determinar o conjunto solução de uma equação diofantina, encontra-se primeiramente uma solução particular, e combina-se a mesma com a solução da equação homogênea (no caso, $ax+by=0\,\!$)

Agora é possível resolver o problema proposto no início.

Aplicação

Será que existem números inteiros $x,y,n\,\!$ que verificam $2x+5y=n\,\!$?

Conforme o teorema indica, para que exista uma solução (e portanto infinitas) é preciso que $, mdc(2,5)|n\,\!$.

Pelo algoritmo de Euclides obtem-se $mdc(2,5)=1\,\!$, além de $2\cdot (-2) + 5\cdot 1 = 1\,\!$. Multiplicando ambos os membros por $n\,\!$, segue que:

$2\cdot (-2n) + 5\cdot n = n\,\!$

Assim, as demais soluções são da forma:

• $x = -2n + 5t\,\!$
• $y = n - 2t\,\!$

No contexto em que o problema foi colocado, é exigido que as soluções não sejam números negativos. Disto seguem as seguintes restrições:

• $-2n + 5t\ge 0\,\!$
• $n - 2t\ge 0\,\!$

que são equivalentes a

$\frac{2}{5}n \le t \le \frac{n}{2}\,\!$

Para que exista algum valor inteiro $t\,\!$ nesse intervalo, é suficiente que $\frac{n}{2} - \frac{2}{5}n \ge 1\,\!$, ou seja,

$n = 5n - 4n\ge 10\,\!$

Note que a condição anterior é suficiente, mas não necessária, pois para alguns valores de $n<10\,\!$ também há soluções:

• $4 = 2+2\,\!$
• $5 = 5+0\,\!$
• $6 = 2+2+2\,\!$
• $7 = 5+2\,\!$
• $8 = 2+2+2+2\,\!$
• $9 = 5+2+2\,\!$

A conclusão final é que, utilizando apenas notas de $2\,\!$ e de $5\,\!$ é possível obter qualquer valor inteiro maior que ou igual a $4\,\!$.

Interpretação geométrica

Sabe-se que o conjunto dos pontos $(x,y)\,\!$ (com coordenadas reais) que verificam a equação $d = ax+by\,\!$ é representado por uma reta sobre o plano cartesiano. Então as soluções da equação diofantina $d = ax+by\,\!$, são representadas pelos pontos da reta que possuem ambas as coordenadas inteiras.

Este módulo tem a seguinte tarefa pendente: Incluir figura mostrando uma reta $ax+by=d\,\!$, que passa por vários pontos de coordenadas inteiras, e cujo ponto mais próximo da origem (e com coordenadas inteiras) é destacado.

Diferença de quadrados

Um outro problema que pode ser tratado com as ferramentas desenvolvidas até agora é a busca de soluções inteiras para a seguinte equação:

$n = x^2 - y^2\,\!$

Buscar tais soluções significa determinar se existe algum inteiro $n\,\!$ que pode ser escrito como soma de dois quadrados perfeitos. Se a resposta for afirmativa, será interessante saber exatamente quais são os números inteiros $n\,\!$ que são soma de quadrados.

Estes são alguns exemplos desse tipo de problema:

• $x^2 - y^2 = 30\,\!$ tem soluções inteiras?
• $x^2 - y^2 = 32\,\!$ tem soluções inteiras?

Para poder entender a estratégia para a resolução desse tipo de problema, considere que a segunda equação tenha alguma solução $x,y\,\!$:

$32 = x^2 - y^2\,\!$

O que se pode afirmar sobre esses dois números inteiros?

Primeiramente, deve valer $32 = x^2 - y^2 = (x+y)(x-y)\,\!$, ou seja, a soma e a diferença das soluções devem ser divisores de $32\,\!$. Sabe-se, por exemplo, que $32 = 8 \cdot 4\,\!$. Será que existem inteiros $x,y\,\!$ tais que

• $x + y = 8\,\!$
• $x - y = 4\,\!$

Por inspeção, percebe-se que $x=6\,\!$ e $y=2\,\!$ servem, logo $32=6^2 - 2^2 = 36 - 4\,\!$.

E quanto ao outro problema?

É possível encontrar um par de divisores de $30\,\!$ (por exemplo, $d\,\!$ e $\frac{30}{d}\,\!$) tais que um seja a soma, e outro a diferença das soluções?

Observe:

Divisores de $30\,\!$
$d\,\!$	$\frac{30}{d}\,\!$
$1\,\!$	$30\,\!$
$2\,\!$	$15\,\!$
$3\,\!$	$10\,\!$
$5\,\!$	$6\,\!$

Você é capaz de encontrar alguma linha dessa tabela contendo a soma e a diferença de dois números inteiros? Justifique.

Em vez de continuar tratando o problema baseando-se em exemplos particulares, considere que existem $x,y\,\!$ satisfazeno a equação em sua forma geral:

$n = x^2 - y^2\,\!$

Conforme anteriormente, conclui-se que, para alguma escolha de $u, v\,\!$, tais que $n = u \cdot v\,\!$, tem-se $u=x+y\,\!$ e $v=x-y\,\!$, ou seja, para tais divisores de $n\,\!$ existe uma solução $x,y\,\!$ para o sistema:

$\left\{\begin{matrix} x + y & = & u\\ x - y & = & v\\ \end{matrix}\right.\,\!$

Equivalentemente, tais inteiros $x,y\,\!$ são também solução do sistema:

$\left\{\begin{matrix} 2x & = & u + v\\ 2y & = & u - v\\ \end{matrix}\right.\,\!$

Se você interpretar essas equações adequadamente, concluirá que $u,v\,\!$ devem ter a mesma paridade (ser ambos pares ou ambos ímpares). De fato, se um deles for par e o outro for ímpar, sua soma será um número ímpar, e consequentemente não poderá ser escrita como $2x\,\!$, para nenhum valor inteiro $x\,\!$.

Na verdade, com pouca ou nenhuma argumentação extra, prova-se a validade do seguinte teorema

Teorema

Teorema

Um número inteiro $n\,\!$ pode ser escrito como a diferença de dois quadrados perfeitos, $n = x^2 - y^2\,\!$, se e somente se $n\,\!$ é ímpar ou múltiplo de $4\,\!$.

Demonstração

A argumentação precedente mostrou que se $n = x^2 - y^2\,\!$ então $n=u\cdot v\,\!$, sendo que $u,v\,\!$ têm a mesma paridade. Reciprocamente, se $u,v\,\!$ têm a mesma paridade, então sua soma e sua diferença são números pares, significando que o sistema $\left\{\begin{matrix} 2x & = & u + v\\ 2y & = & u - v\\ \end{matrix}\right.\,\!$ possui uma solução. Mas o conjunto solução deste sistema coincide com o de: $\left\{\begin{matrix} x + y & = & u\\ x - y & = & v\\ \end{matrix}\right.\,\!$ Logo, $n = u\cdot v = (x+y)(x-y) = x^2 - y^2\,\!$. Para finalizar a demonstração, note que as paridades de $u,v\,\!$ são iguais se, e somente se: $u,v\,\!$ são ímpares ou $u,v\,\!$ são pares Mas $u,v\,\!$ são ímpares se, e somente se, $n\,\!$ é ímpar. Além disso, para que $u,v\,\!$ sejam pares, é necessário e suficiente que $u=2r\,\!$ e $v=2s\,\!$. Neste caso, $n=u\cdot v = (2r)\cdot (2s) = 4(rs)\,\!$, ou seja, $n\,\!$ é múltiplo de $4\,\!$.

Uma forma direta de obter a representação de $n\,\!$ como diferença de quadrados é a seguinte:

• Se $n\,\!$ é múltiplo de $4\,\!$.

Nessa situação, $n = 4k = (k+1)^2-(k-1)^2\,\!$.

• Se $n\,\!$ é ímpar.

Nesse caso, $n = 2k+1 = (k+1)^2-k^2\,\!$.

Exemplo

Com esse resultado, conclúi-se que não há solução para o problema dado em um exemplo anterior:

• $x^2 - y^2 = 30\,\!$

De fato, $30\,\!$ não é ímpar e nem múltiplo de $4\,\!$.

Por outro lado, usando a fórmula anterior, fica fácil resolver:

• $x^2 - y^2 = 32\,\!$

Como $32 = 4 \cdot 8\,\!$, segue que $32 = (8+1)^2 - (8-1)^2 = 81 - 49\,\!$

Ternos pitagóricos

Um pouco de história Pitágoras foi um matemático e filósofo grego nascido por volta de 570 a.C., na ilha de Samos. Ele é creditado pela demonstração de uma importante relação entre os lados de um triangulo retângulo, hoje conhecida como o teorema de Pitágoras, cujo enunciado é geralmente resumido da seguinte forma: O quadrado sobre a hipotenusa é igual à soma dos quadrados sobre os outros dois lados.

Um terno pitagórico é uma tripla de números inteiros $x, y, z\,\!$ que satisfazem a equação:

$x^2 + y^2 = z^2\,\!$

Por exemplo, $3^2 + 4^2 = 5^2\,\!$, então $3, 4, 5\,\!$ é um terno pitagórico. Obviamente, $0, 0, 0\,\!$ também é um terno pitagórico, mas este último caso é trivial e sem interesse, portanto não será considerado na discussão que segue. O objetivo dessa seção é determinar em que circunstâncias a equação $x^2 + y^2 = z^2\,\!$ tem solução $x, y, z\,\!$ não trivial (não todos nulos).

É possível simplificar a investigação, considerando somento o caso em que $x, y, z\,\!$ são primos entre si. De fato, se $x=dx', y=dy', z=dz'\,\!$ então:

$(dx')^2 + (dy')^2 = (dz')^2 \Leftrightarrow x'^2 + y'^2 = z'^2\,\!$

Na verdade, se $x, y, z\,\!$ for uma solução, então o máximo divisor comum destes números verifica as seguintes igualdades:

$(x, y, z) = (x, y) = (x, z) = (y, z)\,\!$

Justificativa
Fica a cargo do leitor justificar este fato. Sinta-se livre para melhorar a qualidade deste texto, incluindo a justificativa neste módulo.

Em particular, não podem haver $x, y\,\!$ não podem ser ambos pares.

Por outro lado, os inteiros $x, y\,\!$ também não podem ser ambos ímpares.

De fato, se assim ocorresse, valeria:

• $x=2a+1\,\!$, para algum inteiro $a\,\!$
• $y=2b+1\,\!$, para algum inteiro $b\,\!$

Deste modo, elevando cada um destes números ao quadrado, resultaria:

• $x^2=(2a+1)^2 = 4a^2 + 4a + 1\,\!$ e
• $x^2=(2b+1)^2 = 4b^2 + 4b + 1\,\!$

Donde:

• $x^2 + y^2=(2b+1)^2 = (4a^2 + 4a + 1) + (4b^2 + 4b + 1) = 4k + 2\,\!$

Ou seja, a soma dos quadrados de $x\,\!$ e $y\,\!$ seria par, mas não pertenceria a $4\mathbb{Z}\,\!$.

No entanto, sempre que $z^2\,\!$ é par, tem-se $z\,\!$ par e consequentemente $z^2\in 4\mathbb{Z}\,\!$.

Logo, quando $x, y\,\!$ são ambos ímpares, a soma de seus quadrados não pode ser um quadrado perfeito.

Segue que dos inteiros $x, y\,\!$, um é ímpar e outro é par. Sem perda de generalidade, pode-se supor que $x\,\!$ é par e $y\,\!$ é ímpar.

Uma outra forma de escrever a equação original é:

$x^2 = z^2 - y^2 = (z+y)(z-y)\,\!$

A partir daí, pode-se deduzir outras informações sobre os inteiros que a satisfazem. Por exemplo, $(z+y, z-y) = 1\,\!$, pois:

$d|z+y, z-y \Rightarrow d|2z, 2y \Rightarrow d|2\,\!$

A segunda implicação vale pois $(z,y) = 1\,\!$. Logo, $d \le 2\,\!$.

Mas não pode ocorrer $d=2\,\!$, senão:

$2|z+y\,\!$

e como $y\,\!$ é par, $z\,\!$ também seria, coisa que não é possível já que $(z,y) = 1\,\!$.

Assim, o quadrado perfeito $x^2\,\!$ é o produto de dois números primos entre si. Disso decorre que cada um deles deve ser um quadrado perfeito (veja o exercício 1), ou seja:

$\left\{\begin{matrix} z+y & = & u^2\\ z-y & = & v^2 \end{matrix}\right.\,\!$

que equivale a:

$\left\{\begin{matrix} 2z & = & u^2 + v^2\\ 2y & = & u^2 - v^2 \end{matrix}\right.\,\!$

Portanto, quando três números inteiros primos entre si (e não todos nulos) satizfazem a equação:

$x^2 + y^2 = z^2\,\!$

devem existir inteiros $u,v\,\!$, ímpares e primos entre si, tais que $u>v\,\!$ e:

$\left\{\begin{matrix} x & = & uv\\ y & = & \frac{u^2 - v^2}{2}\\ z & = & \frac{u^2 + v^2}{2} \end{matrix}\right.\,\!$

Claramente, para quaisquer inteiros $u, v\,\!$, os valores de $x, y, z\,\!$ obtidos pelas fórmulas acima são ternos pitagóricos, pois:

$(uv)^2 + (\frac{u^2 - v^2}{2})^2 = \frac{2u^2v^2 + (u^2 - v^2)^2}{2} = \frac{u^2 + v^2}{2}\,\!$

Exemplos

Pode-se obter facilmente uma dezena de ternos pitagóricos utilizando as fórmulas:

$\left\{\begin{matrix} x & = & uv\\ y & = & \frac{u^2 - v^2}{2}\\ z & = & \frac{u^2 + v^2}{2} \end{matrix}\right.\,\!$

Alguns deles são listados na tabela a seguir:

parâmetros		ternos pitagóricos
$u\,\!$	$v\,\!$	$x\,\!$	$y\,\!$	$z\,\!$
3	1	3	4	5
5	1	5	12	13
7	1	7	24	25
9	1	9	40	41
5	3	15	8	17
7	3	21	20	29

Note ainda que toda solução é da forma:

$4UV + (U-V) = (U+V)^2\,\!$

onde:

$\left\{\begin{matrix} U & = & u^2\\ V & = & v^2\\ \end{matrix}\right.\,\!$

Observações

A fórmula clássica para a obtenção de ternos pitagóricos é conhecida como Fórmula de Euclides, por ter sido apresentada nos Elementos de Euclides é a seguinte:

$\left\{\begin{matrix} x & = & a^2 - b^2\\ y & = & 2ab\\ z & = & a^2 + b^2 \end{matrix}\right.\,\!$

Tal fórmula é equivalente àquela deduzida anteriormente, como se pode verificar facilmente:

Demonstração

De fato, foi mostrado que se $x^2 + y^2 = z^2\,\!$, com $(x,y,z)=1\,\!$ então $x,y\,\!$ não têm a mesma paridade. Adimitindo que $x\,\!$ seja ímpar e que $y\,\!$ seja par, conclui-se que $z\,\!$ é impar e portanto: $y^2 = z^2 - x^2 = (z+x)(z-x)\,\!$ Mas é verdade que $(z+x,z-x)=2\,\!$, pois a soma e a diferença de dois números ímpares são números pares. Donde $\left\{\begin{matrix} z+x & = & 2a^2\\ z-x & = & 2b^2\\ \end{matrix}\right.\,\!$ que é equivalente a: $\left\{\begin{matrix} z & = & a^2 + b^2\\ x & = & a^2 - b^2\\ \end{matrix}\right.\,\!$ sendo que $(a,b) = 1\,\!$ Disso se conclui também que: $y = 2ab\,\!$

Exercícios

1. Mostre que se $a^2 = b\cdot c\,\!$, com $b, c\,\!$ primos entre si, então $b, c\,\!$ são quadrados perfeitos.