RE: [obm-l] ax + by = c

["Frederico Reis Marques de Brito" <fredericor@xxxxxxxxxxx>]

ESsa � uma Equa��o Diofantina.

Como vc mesmo notou o mdc (23, 10 ) =1. Assim, existe uma combina��o linear 
inteira de 10 e 23 dando 1, isto �, existem x* e y* em Z tq  23x* + 10y* = 
1. Multiplique x* e y* por 5 e vc obter� uma solu��o particular da eq. 
diofantina.

� f�cil ver q todas as solu�l�es da eq. ser�o da forma: x = x* - 10k  e y = 
y* + 23k, com k inteiro.

Qq d�vida, escreva novamente ou consulte um �livro de Teor dos Num q tenha 
um cap�tulo sobre eq. diofantinas.

Fred.

>From: "Maur�cio" <briqueabraque@yahoo.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: [obm-l] ax + by = c
>Date: Tue, 14 Jun 2005 21:35:25 -0700 (PDT)
>
>
>   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
>=========================================================================

_________________________________________________________________
MSN Messenger: converse online com seus amigos .  
http://messenger.msn.com.br

=========================================================================
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
=========================================================================