PiR2
Gostaria de reagir a esta mensagem? Crie uma conta em poucos cliques ou inicie sessão para continuar.

Equações Diofantinas - Problema

3 participantes

Ir para baixo

Equações Diofantinas - Problema Empty Equações Diofantinas - Problema

Mensagem por Ss Ter 10 Maio 2011, 19:07

To resolvendo um problema de computação, e necessito saber como resolveria esse tipo de equação diofantina:
Nx - My = Z
Exemplos:
7x - 5y = 3
22x - 15y = 14

Eu necessito saber a menor combinação possivel, de tal forma que o menor entre Nx e My sejam minimo.

OBS: Sempre vai ser possivel resolver a equação.

Ss
Iniciante

Mensagens : 1
Data de inscrição : 09/05/2011
Idade : 27
Localização : São Paulo

Ir para o topo Ir para baixo

Equações Diofantinas - Problema Empty Re: Equações Diofantinas - Problema

Mensagem por Ramon Araújo Ter 10 Maio 2011, 21:36

tomemos o primeiro exemplo.

7x - 5y = 3

a = 7
b = -5
c = 3
A primeira coisa a fazer, para saber se tem solução, é tirar o mdc entre a e b. Se esse mdc dividir "c", entao sabemos que a equação tem solução.

Entao, na equação temos:
7x - 5y = 3

mdc(5,7) = 1 , e 1 divide 3. entao essa equação tem solução.

Entao, atribuimos, arbitrariamente valores para x e y, a fim de achar uma das soluções.
Na equação, vemos facilmente que satifaz a igualdade quando x = 4 e y = 5.

esses valores, chamaremos de x0 e y0.

Então, partimos para a fórmula.

X = x0 + (b/d).t

X = 4 + (-5/1).t
X = 4 - 5.t


Y = y0 - (a/d).t

Y = 5 - (7/1).t
Y = 5 - 7.t


t é um número arbitrário, que sempre satisfará a equação. para verificar usemos t = 2

X = 4 - 5.2
X = 4 - 10
X = -6

Y = 5 - 7.2
Y = 5 - 14
Y = -9

Substituindo na equação original temos:

7x - 5y = 3
7(-6) - 5(-9) = 3
- 42 + 45 = 3 Igualdade correta

Ramon Araújo
Ramon Araújo
Recebeu o sabre de luz
Recebeu o sabre de luz

Mensagens : 107
Data de inscrição : 18/10/2010
Idade : 31
Localização : manaus

Ir para o topo Ir para baixo

Equações Diofantinas - Problema Empty Re: Equações Diofantinas - Problema

Mensagem por Elcioschin Qua 11 Maio 2011, 12:32

Uma solução algébrica

7x - 5y = 3 ----> y = (7x - 3)/5 ----> y = x + (2x - 3)/5 ----> Fazendo s = (2x - 3)/5 ---->

x = (5s + 3)/2 ----> x = 2s + 1 + (s + 1)/2 ----> Fazendo (s + 1)/2 = t ----> s = 2t - 1

x = [5*(2t - 1) + 3]/2 ----> x = 5t - 1

y = [7*(5t - 1) - 3]/5 ----> y = 7t - 2

Agora basta variar t

Por exemplo, para t = 1 ----> x = 4 ----> y = 5 ----> Exatamente o exemplo inicial do Ramon
Elcioschin
Elcioschin
Grande Mestre
Grande Mestre

Mensagens : 68029
Data de inscrição : 15/09/2009
Idade : 76
Localização : Santos/SP

Ir para o topo Ir para baixo

Equações Diofantinas - Problema Empty Re: Equações Diofantinas - Problema

Mensagem por Conteúdo patrocinado


Conteúdo patrocinado


Ir para o topo Ir para baixo

Ir para o topo

- Tópicos semelhantes

 
Permissões neste sub-fórum
Não podes responder a tópicos