[obm-l] ax + by = c

["Maurício" <briqueabraque@xxxxxxxxx>]

  Oi, pessoal,

  Estou lendo um livro de teoria dos números que me
pede como exercício que resolva a equação:

  ax + by = c

para x e y, com a,x,b,y,c inteiros. O livro não diz
como fazer. Como c tem que ser múltiplo do máximo
divisor comum o que eu fiz foi adaptar o algoritmo do
Euclides para calcular o mdc, ou seja, eu calculo o
resto de a/b, depois o resto de b dividido por esse
resto etc., só que a cada passo eu anoto o x e o y que
fornecem cada resto. Por exemplo:

  23x + 10y = 5

  Monto essa tabela de (x,y,c):

1 , 0 , 23
0 , 1 , 10
1 , -2 , 3
-3 , 7 , 1

  Aí é só multiplicar por 5: (x,y) = (-3*5,7*5).
  Esse tipo de equação aparece bastante nos exercícios
que estou fazendo. Existe alguma outra maneira de
resolver, mais simples? Também: é possivel resolver
algo do tipo ax=b(mod m) sem resolver completamente ax
+ km = b?

  Obrigado,
  Maurício



		
__________________________________ 
Discover Yahoo! 
Have fun online with music videos, cool games, IM and more. Check it out! 
http://discover.yahoo.com/online.html
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================