Diofantinas

Disponível somente no TrabalhosFeitos
  • Páginas : 20 (4945 palavras )
  • Download(s) : 0
  • Publicado : 2 de maio de 2012
Ler documento completo
Amostra do texto
2. Equações lineares

2.1

Equações diofantinas

Comecemos com um exemplo. Exemplo 2.1 Suponhamos que só existiam moedas de 15 e de 7 escudos e que eu queria pagar (em dinheiro) uma certa quantia em escudos. Será que é sempre possível? E se só existissem moedas de 12 e de 30 escudos? No primeiro caso, se conseguirmos pagar 1 escudo então também sabemos pagar qualquer quantia: basta repetiro pagamento de 1 escudos as vezes que forem necessárias. Para pagar 1 escudo podemos usar uma moeda de 15 e receber de troco duas moedas de 7. Deste modo, se quisermos pagar 23 escudos podemos usar 23 moedas de 15 e receber de troco 46 moedas de 7. É claro que seria mais simples pagar com 2 moedas de 15 e receber 1 moeda de 7 de troco. No fundo estamos a encontrar soluções inteiras da equação 7x +15y = 1. No segundo caso é claro que qualquer quantia que se consiga pagar é necessariamente múltipla de 6, porque 12 e 30 são múltiplos de 6. Por outro lado podemos pagar 6 escudos usando uma moeda de 30 e recebendo de troco duas moedas de 12. Deste modo podemos fazer o pagamento de qualquer quantia que seja múltipla de 6. Chegamos assim à seguinte definição. Definição 2.2 Uma equação nasvariáveis inteiras x, y do tipo ax + by = c, diz-se uma equação diofantina. 25 com a, b, c ∈ Z

Equações lineares
A palavra diofantina “vem” de Diophantus da Alexandria, matemático grego do século III. É claro que se a = 0 ou b = 0 a equação tem resolução imediata. Por exemplo, se a = 0 e b = 0 então existe solução se b divide c e, nesse caso a solução geral é dada por x qualquer e y = c . Para oscasos “não triviais” temos o seguinte teorema. b Teorema 2.3 Sejam a, b inteiros não ambos nulos, c ∈ Z e d = (a, b). A equação ax + by = c (nas incógnitas inteiras x, y)

tem solução se e só se d divide c. Além disso, se x0 , y0 são tais que ax0 + by0 = c então a solução geral da equação ax + by = c é x = x0 + y = y0 −
b dt a d t,

com t ∈ Z.

Demonstração: Se a ou b é igual a 0 o resultado éimediato. Vejamos o caso em que a = 0 = b. Para a primeira parte do teorema. ⇒ Suponhamos que a equação tem solução e sejam x, y ∈ Z tais que ax+by = c. Então d | ax (porque d | a), d | by (porque d | b) e, portanto d | ax + by = c. ⇐ Suponhamos que d | c e seja k tal que kd = c. Usando o Teorema 1.5, sejam α, β ∈ Z tais que aα + bβ = d. Multiplicando esta última igualdade por k obtemos a(αk) +b(βk) = dk = c, o que mostra que x = αk, y = βk é solução da equação ax + by = c. Para a segunda parte do teorema. Sejam x0 , y0 tais que ax0 + by0 = c. Então, se t ∈ Z, a(x0 + b a ab ab t) + b(y0 − t) = ax0 + t + by0 − t = ax0 + by0 = c, d d d d
b d

o que mostra que x = x0 +

t, y = y0 −

b d

t é solução da equação. 26

Equações lineares
Inversamente, para mostrar que, se x, y ∈ Z sãotais que ax + by = c, então x, y são da forma pretendida basta notar que, ax + by = c ⇐⇒ =⇒ ⇐⇒
a d a d

x+

b d

y
b d

=

ax0 + by0 = c

x0 +

y0 =

c d c d

a b (x − x0 ) + (y − y0 ) = 0 d d a b (x − x0 ) = − (y − y0 ). d d

b Deste modo d divide a (x−x0 ). Usando a alínea h) da Proposição 1.4 e a Proposição d b b 1.6 podemos concluir que d divide (x − x0 ) e, portantoexiste t ∈ Z tal que x − x0 = d t. b b b Substituindo na igualdade a (x − x0 ) = − d (y − y0 ) obtemos a d t = − d (y − y0 ) ou seja d d b y − y0 = − a t. Conclusão, existe t ∈ Z tal que x = x0 + d t e y = y0 − a t. d d

Voltemos ao Exemplo 2.1. Uma vez que a equação 15x + 7y = 17 tem como solução x = 3, y = −4 (por exemplo), para pagar 17 escudos, basta pagar com 3 moedas de 15 escudos e receberde troco 4 moedas de 7 escudos. Outra hipótese seria pagar com 11 moedas de 7 escudos e receber de troco 4 moedas de 15 escudos. É claro que o teorema anterior dá-nos um método de encontrar todas as soluções possíveis. Nota 2.4 Note-se que, se encontrarmos por algum meio (tentativas, observação, algum meio sistemático), uma solução de uma equação do tipo ax + by = c então podemos sempre...
tracking img