Diferenças entre edições de "Teoria de números/Equações diofantinas"

Desfeita a edição 260382 de Auxto (Discussão): estava certo (pois a'(x-x_0)=-b'(y-y_0) resulta das igualdades anteriores); -hack obsoleto
(Desfeita a edição 260382 de Auxto (Discussão): estava certo (pois a'(x-x_0)=-b'(y-y_0) resulta das igualdades anteriores); -hack obsoleto)
 
 
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.
 
 
Matematicamente, o que se quer saber é:
Quais os valores de <math>n\,\!</math>, para os quais a solução <math>2x+5y = n\,\!</math> 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 [[w:equação diofantina|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: <math>ax+by = n\,\!.</math>. Aqui, os inteiros <math>a\,\!</math> e <math>b\,\!</math> são fixados.
 
A equação que surgiu do exemplo apresentado no início do capítulo é apenas um caso particular da seguinte: <math>ax+by = n\,\!</math>. Aqui, os inteiros <math>a\,\!</math> e <math>b\,\!</math> são fixados.
 
Quando é que tal equação possui solução?
 
{{Teorema
|Dados <math>a,b \in \mathbb{Z}\,\!</math>, existem <math>x,y \in \mathbb{Z}\,\!</math> tais que <math>ax+by = n\,\!</math> se, e somente se, <math>d = (a,b)|n\,\!.</math>.
 
Além disso, se <math>(x_0,y_0)\,\!</math> é solução, então todas as soluções são da forma:
<math>x = x_0 - b't\,\!</math> e <math>y = y_0 +a't\,\!</math>, onde <math>a=a'd\,\!</math> e <math>b=b'd\,\!.</math>.
}}
{{Demonstração
|Primeiramente, observe que se <math>(x,y)\,\!</math> é uma solução, então <math>d|ax+by = n\,\!</math> (pela linearidade da divisibilidade).
 
Reciprocamente, se <math>d|n\,\!</math>, então <math>n=n'd\,\!.</math>.
 
Mas pelo teorema de Bézout, existem inteiros <math>r,s\,\!</math> tais que <math>ar+bs=d\,\!.</math>. Logo, multiplicando cada membro por <math>n'\,\!</math>, tem-se:
:<math>n'(ar+bs)=n'd=n\,\!</math>
ou seja, basta tomar <math>x=n'r\,\!</math> e <math>y=n's\,\!</math>, e <math>(x,y)\,\!</math> será uma solução.
 
 
Resta determinar a forma geral de todas as soluções.
 
Se <math>(x_0,y_0)\,\!</math> for uma solução conhecida, qualquer outra solução <math>(x,y)\,\!</math> satizfaz:
:<math>n = ax+by=ax_0+by_0\,\!</math>
 
Então <math>a(x-x_0)+b(y-y_0)=0\,\!</math>, ou seja, <math>a(x-x_0)=-b(y-y_0)\,\!.</math>.
 
Tomando <math>d=(a,b)\,\!</math> é possível escrever
* <math>a=a'd\,\!</math>
* <math>b=b'd\,\!</math>
Donde:
Onde:
:<math>a'(x-x_0)=-b'(y-y_0)\,\!</math>
 
Claramente <math>(a',b')=1\,\!</math> e <math>a'|-b'(y-y_0)\,\!.</math>.
 
Logo
:<math>a'|(y-y_0)\,\!</math>
ou seja, existe <math>t \in \mathbb{Z}\,\!</math> tal que
:<math>a't=y-y_0\,\!</math>
 
Portanto, <math>y=y_0+a't\,\!</math>
 
Usando essa expressão em
:<math>a'(x-x_0) = -b'(y-y_0)\,\!</math>
resulta
:<math>a'(x-x_0) = -b'(y_0+a't-y_0) = -b'a't\,\!</math>
 
Disto se conclui que <math>x=x_0-b't\,\!.</math>.
}}
 
Assim como acontece em problemas que envolvem [[w:equações diferenciais|equações diferenciais]], para determinar o [[w:conjunto soluçã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, <math>ax+by=0\,\!</math>)
 
Agora é possível resolver o problema proposto no início.
 
=== Aplicação ===
Será que existem números inteiros <math>x,y,n\,\!</math> que verificam <math>2x+5y=n\,\!?</math>?
 
Conforme o teorema indica, para que exista uma solução (e portanto infinitas) é preciso que <math>, mdc(2,5)|n\,\!.</math>.
 
Pelo algoritmo de Euclides obtem-se <math>mdc(2,5)=1\,\!</math>, além de <math>2\cdot (-2) + 5\cdot 1 = 1\,\!.</math>. Multiplicando ambos os membros por <math>n\,\!</math>, segue que:
:<math>2\cdot (-2n) + 5\cdot n = n\,\!</math>
Assim, as demais soluções são da forma:
* <math>x = -2n + 5t\,\!</math>
* <math>y = n - 2t\,\!</math>
 
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:
* <math>-2n + 5t\ge 0\,\!</math>
* <math>n - 2t\ge 0\,\!</math>
 
que são equivalentes a
:<math>\frac{2}{5}n \le t \le \frac{n}{2}\,\!</math>
 
Para que exista algum valor inteiro <math>t\,\!</math> nesse intervalo, é suficiente que <math>\frac{n}{2} - \frac{2}{5}n \ge 1\,\!</math>, ou seja,
:<math>n = 5n - 4n\ge 10\,\!</math>
 
Note que a condição anterior é suficiente, mas não necessária, pois para alguns valores de <math>n<10\,\!</math> também há soluções:
* <math>4 = 2+2\,\!</math>
* <math>5 = 5+0\,\!</math>
* <math>6 = 2+2+2\,\!</math>
* <math>7 = 5+2\,\!</math>
* <math>8 = 2+2+2+2\,\!</math>
* <math>9 = 5+2+2\,\!</math>
 
A conclusão final é que, utilizando apenas notas de <math>2\,\!</math> e de <math>5\,\!</math> é possível obter qualquer valor inteiro maior que ou igual a <math>4\,\!.</math>.
 
=== Interpretação geométrica ===
Sabe-se que o conjunto dos pontos <math>(x,y)\,\!</math> (com coordenadas reais) que verificam a equação <math>d = ax+by\,\!</math> é representado por uma reta sobre o plano cartesiano. Então as soluções da [[w:Equação diofantina|equação diofantina]] <math>d = ax+by\,\!</math>, são representadas pelos pontos da reta que possuem ambas as coordenadas inteiras.
 
{{Tarefa|Incluir figura mostrando uma reta <math>ax+by=d\,\!</math>, que passa por vários pontos de coordenadas inteiras, e cujo ponto mais próximo da origem (e com coordenadas inteiras) é destacado.}}
Sabe-se que o conjunto dos pontos <math>(x,y)\,\!</math> (com coordenadas reais) que verificam a equação <math>d = ax+by\,\!</math> é representado por uma reta sobre o plano cartesiano. Então as soluções da [[w:Equação diofantina|equação diofantina]] <math>d = ax+by\,\!</math>, são representadas pelos pontos da reta que possuem ambas as coordenadas inteiras.
 
{{Tarefa|Incluir figura mostrando uma reta <math>ax+by=d\,\!</math>, 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:
:<math>n = x^2 - y^2\,\!</math>
 
Buscar tais soluções significa determinar se existe algum inteiro <math>n\,\!</math> que pode ser escrito como soma de dois [[w:Quadrado perfeito|quadrados perfeitos]]. Se a resposta for afirmativa, será interessante saber ''exatamente'' quais são os números inteiros <math>n\,\!</math> que são soma de quadrados.
 
Estes são alguns exemplos desse tipo de problema:
*<math>x^2 - y^2 = 30\,\!</math> tem soluções inteiras?
*<math>x^2 - y^2 = 32\,\!</math> 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 <math>x,y\,\!:</math>:
:<math>32 = x^2 - y^2\,\!</math>
 
O que se pode afirmar sobre esses dois números inteiros?
 
Primeiramente, deve valer <math>32 = x^2 - y^2 = (x+y)(x-y)\,\!</math>, ou seja, a soma e a diferença das soluções devem ser divisores de <math>32\,\!.</math>. Sabe-se, por exemplo, que <math>32 = 8 \cdot 4\,\!.</math>. Será que existem inteiros <math>x,y\,\!</math> tais que
* <math>x + y = 8\,\!</math>
* <math>x - y = 4\,\!</math>
Por inspeção, percebe-se que <math>x=6\,\!</math> e <math>y=2\,\!</math> servem, logo <math>32=6^2 - 2^2 = 36 - 4\,\!.</math>.
 
E quanto ao outro problema?
 
É possível encontrar um par de divisores de <math>30\,\!</math> (por exemplo, <math>d\,\!</math> e <math>\frac{30}{d}\,\!</math>) tais que um seja a soma, e outro a diferença das soluções?
 
Observe:
:{| class="wikitable" style="text-align:center"
!colspan="2" | Divisores de <math>30\,\!</math>
|-
|<math>d\,\!</math> || <math>\frac{30}{d}\,\!</math>
|-
|<math>1\,\!</math> || <math>30\,\!</math>
|-
|<math>2\,\!</math> || <math>15\,\!</math>
|-
|<math>3\,\!</math> || <math>10\,\!</math>
|-
|<math>5\,\!</math> || <math>6\,\!</math>
|}
 
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 <math>x,y\,\!</math> satisfazeno a equação em sua forma geral:
:<math>n = x^2 - y^2\,\!</math>
 
Conforme anteriormente, conclui-se que, para alguma escolha de <math>u, v\,\!</math>, tais que <math>n = u \cdot v\,\!</math>, tem-se <math>u=x+y\,\!</math> e <math>v=x-y\,\!</math>, ou seja, para tais divisores de <math>n\,\!</math> existe uma solução <math>x,y\,\!</math> para o sistema:
:<math>\left\{\begin{matrix}
x + y & = & u\\
x - y & = & v\\
\end{matrix}\right.\,\!</math>
 
Equivalentemente, tais inteiros <math>x,y\,\!</math> são também solução do sistema:
:<math>\left\{\begin{matrix}
2x & = & u + v\\
2y & = & u - v\\
\end{matrix}\right.\,\!</math>
 
Se você interpretar essas equações adequadamente, concluirá que <math>u,v\,\!</math> 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 <math>2x\,\!</math>, para nenhum valor inteiro <math>x\,\!.</math>.
 
Na verdade, com pouca ou nenhuma argumentação extra, prova-se a validade do seguinte teorema
 
=== Teorema ===
{{Teorema
|Um número inteiro <math>n\,\!</math> pode ser escrito como a diferença de dois quadrados perfeitos, <math>n = x^2 - y^2\,\!</math>, se e somente se <math>n\,\!</math> é ímpar ou múltiplo de <math>4\,\!.</math>.
}}
{{Demonstração
|A argumentação precedente mostrou que se <math>n = x^2 - y^2\,\!</math> então <math>n=u\cdot v\,\!</math>, sendo que <math>u,v\,\!</math> têm a mesma paridade.
 
Reciprocamente, se <math>u,v\,\!</math> têm a mesma paridade, então sua soma e sua diferença são números pares, significando que o sistema
:<math>\left\{\begin{matrix}
2x & = & u + v\\
2y & = & u - v\\
\end{matrix}\right.\,\!</math>
 
possui uma solução. Mas o conjunto solução deste sistema coincide com o de:
x + y & = & u\\
x - y & = & v\\
\end{matrix}\right.\,\!</math>
Logo, <math>n = u\cdot v = (x+y)(x-y) = x^2 - y^2\,\!.</math>.
 
Para finalizar a demonstração, note que as paridades de <math>u,v\,\!</math> são iguais se, e somente se:
# <math>u,v\,\!</math> são ''ímpares'' ou
# <math>u,v\,\!</math> são ''pares''
 
Mas <math>u,v\,\!</math> são ímpares se, e somente se, <math>n\,\!</math> é ímpar.
Além disso, para que <math>u,v\,\!</math> sejam pares, é necessário e suficiente que <math>u=2r\,\!</math> e <math>v=2s\,\!.</math>. Neste caso, <math>n=u\cdot v = (2r)\cdot (2s) = 4(rs)\,\!</math>, ou seja, <math>n\,\!</math> é múltiplo de <math>4\,\!.</math>.
}}
 
Uma forma direta de obter a representação de <math>n\,\!</math> como diferença de quadrados é a seguinte:
* Se <math>n\,\!</math> é múltiplo de <math>4\,\!.</math>.
:Nessa situação, <math>n = 4k = (k+1)^2-(k-1)^2\,\!.</math>.
* Se <math>n\,\!</math> é ímpar.
:Nesse caso, <math>n = 2k+1 = (k+1)^2-k^2\,\!.</math>.
 
=== Exemplo ===
 
Com esse resultado, conclúi-se que não há solução para o problema dado em um exemplo anterior:
* <math>x^2 - y^2 = 30\,\!</math>
 
De fato, <math>30\,\!</math> não é ímpar e nem múltiplo de <math>4\,\!.</math>.
 
Por outro lado, usando a fórmula anterior, fica fácil resolver:
* <math>x^2 - y^2 = 32\,\!</math>
 
Como <math>32 = 4 \cdot 8\,\!</math>, segue que <math>32 = (8+1)^2 - (8-1)^2 = 81 - 49\,\!</math>
 
== Ternos pitagóricos ==
 
 
{| width="100%" style="border:1px solid #6688AA;-moz-border-radius:1em; background-color:#F0F9FF; margin-left:1em; padding:1em; width:50%; float:right; clear:right; " valign="top"|
|-
|<big><big>Um pouco de história</big></big>
[[ImageImagem:Kapitolinischer Pythagoras adjusted.jpg|120px|right|Bust of Pythagoras of Samos in the Capitoline Museums, Rome]]
[[w:Pitágoras|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 [[w:Teorema de Pitágoras|teorema de Pitágoras]], cujo enunciado é geralmente resumido da seguinte forma:
<center>''O quadrado sobre a hipotenusa é igual à soma dos quadrados sobre os outros dois lados''.</center>
|}
 
Um ''terno pitagórico'' é uma tripla de números inteiros <math>x, y, z\,\!</math> que satisfazem a equação:
:<math>x^2 + y^2 = z^2\,\!</math>
 
Por exemplo, <math>3^2 + 4^2 = 5^2\,\!</math>, então <math>3, 4, 5\,\!</math> é um terno pitagórico. Obviamente, <math>0, 0, 0\,\!</math> 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 <math>x^2 + y^2 = z^2\,\!</math> tem solução <math>x, y, z\,\!</math> não trivial (não todos nulos).
 
É possível simplificar a investigação, considerando somento o caso em que <math>x, y, z\,\!</math> são primos entre si. De fato, se <math>x=dx', y=dy', z=dz'\,\!</math> então:
:<math>(dx')^2 + (dy')^2 = (dz')^2 \Leftrightarrow x'^2 + y'^2 = z'^2\,\!</math>
 
Na verdade, se <math>x, y, z\,\!</math> for uma solução, então o máximo divisor comum destes números verifica as seguintes igualdades:
:<math>(x, y, z) = (x, y) = (x, z) = (y, z)\,\!</math>
{{Justificativa}}
 
Em particular, não podem haver <math>x, y\,\!</math> não podem ser ambos pares.
 
Por outro lado, os inteiros <math>x, y\,\!</math> também não podem ser ambos ímpares.
:De fato, se assim ocorresse, valeria:
:* <math>x=2a+1\,\!</math>, para algum inteiro <math>a\,\!</math>
:* <math>y=2b+1\,\!</math>, para algum inteiro <math>b\,\!</math>
:Deste modo, elevando cada um destes números ao quadrado, resultaria:
:* <math>x^2=(2a+1)^2 = 4a^2 + 4a + 1\,\!</math> e
:* <math>x^2=(2b+1)^2 = 4b^2 + 4b + 1\,\!</math>
:Donde:
:* <math>x^2 + y^2=(2b+1)^2 = (4a^2 + 4a + 1) + (4b^2 + 4b + 1) = 4k + 2\,\!</math>
:Ou seja, a soma dos quadrados de <math>x\,\!</math> e <math>y\,\!</math> seria par, mas não pertenceria a <math>4\mathbb{Z}\,\!.</math>.
:No entanto, sempre que <math>z^2\,\!</math> é par, tem-se <math>z\,\!</math> par e consequentemente <math>z^2\in 4\mathbb{Z}\,\!.</math>.
:Logo, quando <math>x, y\,\!</math> são ambos ímpares, a soma de seus quadrados não pode ser um quadrado perfeito.
 
Segue que dos inteiros <math>x, y\,\!</math>, um é ímpar e outro é par. Sem perda de generalidade, pode-se supor que <math>x\,\!</math> é par e <math>y\,\!</math> é ímpar.
 
Uma outra forma de escrever a equação original é:
:<math>x^2 = z^2 - y^2 = (z+y)(z-y)\,\!</math>
 
A partir daí, pode-se deduzir outras informações sobre os inteiros que a satisfazem. Por exemplo, <math>(z+y, z-y) = 1\,\!</math>, pois:
:<math>d|z+y, z-y \Rightarrow d|2z, 2y \Rightarrow d|2\,\!</math>
A segunda implicação vale pois <math>(z,y) = 1\,\!.</math>. Logo, <math>d \le 2\,\!.</math>.
 
Mas não pode ocorrer <math>d=2\,\!</math>, senão:
:<math>2|z+y\,\!</math>
e como <math>y\,\!</math> é par, <math>z\,\!</math> também seria, coisa que não é possível já que <math>(z,y) = 1\,\!.</math>.
 
Assim, o quadrado perfeito <math>x^2\,\!</math> é o produto de dois números primos entre si. Disso decorre que cada um deles deve ser um quadrado perfeito (veja o [[#Exercícios|exercício 1]]), ou seja:
 
:<math>\left\{\begin{matrix}
z+y & = & u^2\\
z-y & = & v^2
\end{matrix}\right.\,\!</math>
 
que equivale a:
2z & = & u^2 + v^2\\
2y & = & u^2 - v^2
\end{matrix}\right.\,\!</math>
 
Portanto, quando três números inteiros primos entre si (e não todos nulos) satizfazem a equação:
:<math>x^2 + y^2 = z^2\,\!</math>
devem existir inteiros <math>u,v\,\!</math>, ímpares e primos entre si, tais que <math>u>v\,\!</math> e:
:<math>\left\{\begin{matrix}
x & = & uv\\
y & = & \frac{u^2 - v^2}{2}\\
z & = & \frac{u^2 + v^2}{2}
\end{matrix}\right.\,\!</math>
 
Claramente, para quaisquer inteiros <math>u, v\,\!</math>, os valores de <math>x, y, z\,\!</math> obtidos pelas fórmulas acima são ternos pitagóricos, pois:
:<math>(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}\,\!</math>
 
=== Exemplos ===
y & = & \frac{u^2 - v^2}{2}\\
z & = & \frac{u^2 + v^2}{2}
\end{matrix}\right.\,\!</math>
 
Alguns deles são listados na tabela a seguir:
!colspan="2" | parâmetros||colspan="3"| ternos pitagóricos
|-
!<math>u\,\!</math> || <math>v\,\!</math> || <math>x\,\!</math> || <math>y\,\!</math> || <math>z\,\!</math>
|-
|3 || 1 || 3 || 4 || 5
 
Note ainda que toda solução é da forma:
:<math>4UV + (U-V) = (U+V)^2\,\!</math>
onde:
:<math>\left\{\begin{matrix}
U & = & u^2\\
V & = & v^2\\
\end{matrix}\right.\,\!</math>
 
=== Observações ===
y & = & 2ab\\
z & = & a^2 + b^2
\end{matrix}\right.\,\!</math>
 
Tal fórmula é equivalente àquela deduzida anteriormente, como se pode verificar facilmente:
{{Demonstração
|De fato, foi mostrado que se <math>x^2 + y^2 = z^2\,\!</math>, com <math>(x,y,z)=1\,\!</math> então <math>x,y\,\!</math> não têm a mesma paridade. Adimitindo que <math>x\,\!</math> seja ímpar e que <math>y\,\!</math> seja par, conclui-se que <math>z\,\!</math> é impar e portanto:
:<math>y^2 = z^2 - x^2 = (z+x)(z-x)\,\!</math>
Mas é verdade que <math>(z+x,z-x)=2\,\!</math>, pois a soma e a diferença de dois números ímpares são números pares.
Donde
:<math>\left\{\begin{matrix}
z+x & = & 2a^2\\
z-x & = & 2b^2\\
\end{matrix}\right.\,\!</math>
 
que é equivalente a:
z & = & a^2 + b^2\\
x & = & a^2 - b^2\\
\end{matrix}\right.\,\!</math>
sendo que <math>(a,b) = 1\,\!</math>
 
Disso se conclui também que:
:<math>y = 2ab\,\!</math>
}}
 
== Exercícios ==
# Mostre que se <math>a^2 = b\cdot c\,\!</math>, com <math>b, c\,\!</math> primos entre si, então <math>b, c\,\!</math> são quadrados perfeitos.
 
{{AutoCat}}