Bom, o difícil é que x, y sejam inteiros positivos (ou talvez não-negativos). Mas a idéia é exatamente essa. Ou seja, dado este ax+by (com x, y inteiros sobre os quais nada sabemos) obter am + bn, com m, n >= 0. E isso só dá para fazer se c for suficientemente grande, pois vamos ter que diminuir um e aumentar o outro.
Abraços, -- Bernardo Freitas Paulo da Costa On Wed, 2 Feb 2005 12:19:34 -0300 (ART), Marcelo Ribeiro <[EMAIL PROTECTED]> wrote: > 1) Eu não entendi o porquê da restrição c>=ab... > Bom, seja d = mdc(a,b). É possível escrever d como combinação linear dos > números a e b, isto é, existem x,y pertencentes a Z de forma que d = ax+by > [isto é um teorema que não lembro como prova]. No nosso caso, temos mdc(a,b) > = 1. Portanto: > > ax+by = 1 > > Agora basta multiplicar por c e ficamos com > > a(cx)+b(cy) = c > > pronto! É possível escrever c como combinação linear de a,b, onde mdc(a,b) = > 1. Corrijam-me se errei em alguma coisa, por favor. =] > abraços > Marcelo > > ________________________________ > Yahoo! Acesso Grátis - Internet rápida e grátis. Instale o discador do > Yahoo! agora. > > ========================================================================= 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 =========================================================================