domingo, 12 de agosto de 2012

Equações diofantinas lineares.

Olá!

O que você acha da equação abaixo?

[;7x+5y=2;]

Acha que não possui solução, que possui somente 1 solução ou acha possui infinitas soluções?

Hoje mostrarei como resolver equações diofantinas lineares. Que são equações da forma [;ax+by=c;] onde x e y são incógnitas.

Antes uma pequena restrição.

A equação [;ax + by=c;] adimite solução se e somente se [;mdc(a,b);] divide [;c;].

Demonstração: Vamos supor que [;x_0;] e [;y_0;] sejam soluções das equações.
Como o [;mdc(a,b);] divide [;a;] e divide [;b;] , então ele divide [;ax_0+by_0=c;].

Agora, suponha que [;mdc(a,b);] divida c. Logo, [;c=d\cdot k;] onde [;d=mdc(a,b);].

Pela relação de Bézout (que você pode ler mais clicando aqui) existem 2 inteiros x e y que satisfazem: [;mdc(a,b)=ax+by;] como [;c=d\cdot k;] então [;mdc(a,b) \cdot k = c = a(x\cdot k) + b(y\cdot k);]

C.Q.D.

Para resolver a equação inicialmente você deve verificar se [;mdc(a,b)=d;] divide [;c;].
Em caso afirmativo, devemos dividir ambos os lados da equação inicial por [;d;] ficando
[;\frac{a}{d}x+\frac{b}{d}y=\frac{c}{d};]
isso vai garantir que a "familia" de soluções que encontrarmos seja composta somente pelas possiveis soluções da equação inicial.

Depois, deve-se procurar uma solução particular para a equação reduzida [;(x_o,y_0);]. E fazer:

[;x=x_0+bt;]
e
[;y= y_0 - at;]

Onde [;t;] é um inteiro qualquer.

De fato isso funciona, pois
[;\frac{a}{d}(x_0 + bt) + \frac{b}{d}(y_0-at)= \frac{a}{d}x_0 + \frac{abt}{d} + \frac{b}{d}y_0 - \frac{bat}{d}=\frac{a}{d} x_0 + \frac{b}{d} y_0=\frac{c}{d};]

No caso da equação que apresentei no inicio do problema, [;mdc(7,5)=1;] e a solução particular é
[;(x_0,y_0)=(1,-1);] logo,

[;x=1+5t;]
e
[;y=-1-7t;]

Observe que como a solução fica em função de um parâmetro t, sempre que ela tiver alguma solução, então ela terá infinitas.

Bem, por hoje é só! Por favor, avalie a postagem logo abaixo,sua opinião é muito importante para nós. Se você gostou do blog, compartilhe com seus amigos nas redes sociais e se inscreva por e-mail para receber nossas atualizações.

Até mais!

6 comentários:

  1. Faltou mais exemplos e exercícios :(...No mais, gostei da explicação

    ResponderExcluir
    Respostas
    1. Bem, isso é algo que eu já tinha notado. O blog esta meio parado, esperamos voltar com ele ainda nesse verão, que dedicarei a concertar alguns erros conceituais que eu possa ter cometido, situações que eu não tenha abordado e colocar exercícios em todos (ou na maioria) dos post. Obrigado pela sugestão. Eduardo

      Excluir
  2. Não entendi muito bem essa última parte: Observe que sempre que ela tiver alguma solução, então ela terá infinitas soluções.

    ResponderExcluir
    Respostas
    1. Por que você deixa a sua solução (X = X0 + bt Y = Y0 - at)em função de um parâmetro t que é um número inteiro (portanto tem infinitos valores).

      Excluir
  3. E se os números forem primos entre si? responda pf, ok.

    ResponderExcluir
    Respostas
    1. Você quis dizer se o mdc(a,b) não dividir c? Bem, então ela não terá solução. Para demonstrar, suponha por absurdo que ela terá solução.

      Vamos supor que o mdc(a,b) não divide c, mas que existe uma solução (X,Y) tal que
      aX + bY = c.
      Observe que se mdc(a,b) = d, então a=d.k e b= d.l logo,
      com aX + bY = c temos d.k.X + d.l.Y = c o que implica que d.(kX + lY)=c

      o que implica que d divide c, ou, de outra forma, mdc(a,b)=d divide c. Mas por hipótese mdc(a,b) não divide c. ABSURDO. Assim, se mdc(a,b) não divide c, então a equação não terá solução.

      Agora, se vc quis saber o que acontece se a e b forem primos entre si ? Nesse caso mdc(a,b)=1 logo, como 1 divide qualquer número, mdc(a,b) com certeza dividirá c e a equação terá solução.

      Espero ter respondido a sua dúvida.

      Até mais e obrigado pelo comentário,
      dudu

      Excluir

Você pode comentar! A equipe do blog encoraja todos a comentar.

Porém, lembre-se que comentários que desrespeitem as regras abaixo serão excluídos:

-É proibido ofender qualquer pessoa ou grupo em seu comentário.
-Os comentários deverão ser minimamente relacionados com o tópico. Lembrem-se, estamos falando de um blog de matemática!
-Proibido flood.
-Proibido palavras de baixo calão.
-Proibido colocar qualquer tipo de conteúdo improprio para menores de 18 anos (há menores de idade que acessam o blog).

A equipe do blog agradece seu comentário, e tenha certeza que será muito enriquecedor. Tentaremos respondê-los o quanto antes possível.

Related Posts Plugin for WordPress, Blogger...