Olá!
O que você acha da equação abaixo?
![[;7x+5y=2;]](http://thewe.net/tex/7x+5y=2 "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;]](http://thewe.net/tex/ax+by=c "ax+by=c")
onde x e y são incógnitas.
Antes uma pequena restrição.
A equação![[;ax + by=c;]](http://thewe.net/tex/ax%20+%20by=c "ax + by=c")
adimite solução se e somente se ![[;mdc(a,b);]](http://thewe.net/tex/mdc%28a,b%29 "mdc(a,b)")
divide ![[;c;]](http://thewe.net/tex/c "c")
.
Demonstração: Vamos supor que![[;x_0;]](http://thewe.net/tex/x_0 "x_0")
e ![[;y_0;]](http://thewe.net/tex/y_0 "y_0")
sejam soluções das equações.
Como o divide ![[;a;]](http://thewe.net/tex/a "a")
e divide ![[;b;]](http://thewe.net/tex/b "b")
, então ele divide ![[;ax_0+by_0=c;]](http://thewe.net/tex/ax_0+by_0=c "ax_0+by_0=c")
.
Agora, suponha que divida c. Logo, ![[;c=d\cdot k;]](http://thewe.net/tex/c=d%5Ccdot%20k "c=d\cdot k")
onde ![[;d=mdc(a,b);]](http://thewe.net/tex/d=mdc%28a,b%29 "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;]](http://thewe.net/tex/mdc%28a,b%29=ax+by "mdc(a,b)=ax+by")
como então ![[;mdc(a,b) \cdot k = c = a(x\cdot k) + b(y\cdot k);]](http://thewe.net/tex/mdc%28a,b%29%20%5Ccdot%20k%20=%20c%20=%20a%28x%5Ccdot%20k%29%20+%20b%28y%5Ccdot%20k%29 "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;]](http://thewe.net/tex/mdc%28a,b%29=d "mdc(a,b)=d")
divide .
Em caso afirmativo, devemos dividir ambos os lados da equação inicial por![[;d;]](http://thewe.net/tex/d "d")
ficando
![[;\frac{a}{d}x+\frac{b}{d}y=\frac{c}{d};]](http://thewe.net/tex/%5Cfrac%7Ba%7D%7Bd%7Dx+%5Cfrac%7Bb%7D%7Bd%7Dy=%5Cfrac%7Bc%7D%7Bd%7D "\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);]](http://thewe.net/tex/%28x_o,y_0%29 "(x_o,y_0)")
. E fazer:
![[;x=x_0+bt;]](http://thewe.net/tex/x=x_0+bt "x=x_0+bt")
e
![[;y= y_0 - at;]](http://thewe.net/tex/y=%20y_0%20-%20at "y= y_0 - at")
Onde![[;t;]](http://thewe.net/tex/t "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};]](http://thewe.net/tex/%5Cfrac%7Ba%7D%7Bd%7D%28x_0%20+%20bt%29%20+%20%5Cfrac%7Bb%7D%7Bd%7D%28y_0-at%29=%20%5Cfrac%7Ba%7D%7Bd%7Dx_0%20+%20%5Cfrac%7Babt%7D%7Bd%7D%20+%20%5Cfrac%7Bb%7D%7Bd%7Dy_0%20-%20%5Cfrac%7Bbat%7D%7Bd%7D=%5Cfrac%7Ba%7D%7Bd%7D%20x_0%20+%20%5Cfrac%7Bb%7D%7Bd%7D%20y_0=%5Cfrac%7Bc%7D%7Bd%7D "\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;]](http://thewe.net/tex/mdc%287,5%29=1 "mdc(7,5)=1")
e a solução particular é
![[;(x_0,y_0)=(1,-1);]](http://thewe.net/tex/%28x_0,y_0%29=%281,-1%29 "(x_0,y_0)=(1,-1)")
logo,
![[;x=1+5t;]](http://thewe.net/tex/x=1+5t "x=1+5t")
e
![[;y=-1-7t;]](http://thewe.net/tex/y=-1-7t "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!
O que você acha da equação abaixo?
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
Antes uma pequena restrição.
A equação
Demonstração: Vamos supor que
Como o
Agora, suponha que
Pela relação de Bézout (que você pode ler mais clicando aqui) existem 2 inteiros x e y que satisfazem:
C.Q.D.
Para resolver a equação inicialmente você deve verificar se
Em caso afirmativo, devemos dividir ambos os lados da equação inicial por
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
e
Onde
De fato isso funciona, pois
No caso da equação que apresentei no inicio do problema,
e
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!
Faltou mais exemplos e exercícios :(...No mais, gostei da explicação
ResponderExcluirBem, 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
ExcluirNão entendi muito bem essa última parte: Observe que sempre que ela tiver alguma solução, então ela terá infinitas soluções.
ResponderExcluirPor 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).
ExcluirE se os números forem primos entre si? responda pf, ok.
ResponderExcluirVocê 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.
ExcluirVamos 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