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