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

Insira o enunciado do teorema.

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 portant infinitas) é preciso que $(2,5)|n\,\!$.

Pelo algoritmo de Euclides obtem-se $(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\geq 0\,\!$
• $n-2t\geq 0\,\!$

que são equivalentes a

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

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

$n=5n-4n\geq 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

Insira o enunciado do teorema.

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=4t+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 terno pitagórico é uma tripla de números inteiros $x,y,z\,\!$ que satisfazem a equação:

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

Essa denominação é utilizada em homenagem a Pitágoras, um matemático grego nascido por volta de 570 a.C., na ilha de Samos. Pitágoras é 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.