Teoria de números/Equações diofantinas

Origem: Wikilivros, livros abertos por um mundo aberto.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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.


Crystal Clear app kaddressbook.png 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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:

  1. u,v são ímpares ou
  2. 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[editar | editar código-fonte]

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[editar | editar código-fonte]

Um pouco de história
Bust of Pythagoras of Samos in the Capitoline Museums, Rome

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[editar | editar código-fonte]

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[editar | editar código-fonte]

Wikipedia
A Wikipédia tem mais sobre este assunto:
Terno pitagórico

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[editar | editar código-fonte]

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