Re: Problema de inteiros

["José Paulo Carneiro" <jpcarneiro@xxxxxxxxxxxxxxx>]

O Teorema de Bezout (por alguns chamado de Teorema Fundamental da
Teoria dos Numeros) diz que dados dois inteiros a e b, eh possivel (usando o
algoritmo de Euclides, por exemplo) encontrar dois inteiros r e s tais que
ra+sb=m.d.c(a,b). [Veja RPM no 37, p.27: "Dispositivo pratico para expressar
o mdc de dois numeros como combinacao linear deles"].
Em particular, se a e b e forem primos entre si, pode-se achar r e s tais
que
ra+sb=1 e, portanto:  (r n)a+ (sn)b = n, onde n eh um numero qualquer dado.


PS: Eu ja tinha escrito este e-mail quando vi que o Marcos Paulo falou a
mesma coisa. That's my boy!

-----Mensagem original-----
De: Ecass Dodebel <ecassdodebel@hotmail.com>
Para: obm-l@mat.puc-rio.br <obm-l@mat.puc-rio.br>
Data: Sábado, 22 de Abril de 2000 18:05
Assunto: Problema de inteiros


>E ai, pessoal?
>
>Eu estava tentando resolver um dos problemas propostos na última Eureka! e
>acabei chegando em uma parte que consigo seguir adiante mas é muito
>trabalhosa a minha prova, e não sei se está bem certa. Lá vai.
>
>1) Sejam x e y dois números primos entre si. Provar que podemos obter
>qualquer número somando múltiplos de x e de y.
>
>Solução.
>Queremos provar que para todo o x,y,n dados, podemos achar f e g de modo
que
>
>fx + gy = n  ( a soma de múltiplos de x e de y dão o n )
>
>Isola-se o f, ou o g... no caso isolei o f:
>
>f = (n - gy)/x
>
>Agora nos basta encontrar g de modo que x | n - gy. Para quem sabe um
>pouquinho de Teoria dos Números, eu acho que se variarmos o y num s.c.r.
>então o n - gy será um s.c.r. módulo x, e estaria provado. Mas vamos por
>partes:
>
>Suponhamos que
>
>n - g1y =/= n - g2y (mod x)    '=/= incongruente
>g1y =/= g2y (mod x)  ==> afirmação similar a x não divide y(g1-g2)
>
>Como  mdc(x,y)=1 então
>
>g1 =/= g2 (mod x)
>
>Vale tambem que se g1 =/= g2 (mod x) então n - g1y =/= n - g2y (mod x).
>Agora escolhemos x números incongruentes módulo x (g1,...,gx), ou seja, que
>nunca deixem o mesmo resto na divisão por x. E necessariamente:
>
>n - giy =/= n - gjy (mod x) para todo o i e j
>
>Ou seja, nesses x números (n-g1y,...,n-gxy), todos são incongruentes módulo
>x, e como existem apenas x restos possíveis na divisão por x,
>necessariamente algum deles deixará resto zero na divisão por x, e portanto
>haverá um g, tal que:
>
>f = (n - gy)/x será inteiro, e está provado o enunciado.
>
>2) Sejam x e y dois números primos entre si. Prove que existe um N, de modo
>que para todo o n > N, podemos escolher múltiplos positivos de x e de y que
>somados dão n. Nessas condições teremos que ter
>
>Solução.
>O problema pede para que mostremos que existem f e g positivos de modo que,
>para n > N
>
>fx + gy = n  (lembrando que é todo mundo inteiro nesse e-mail)
>
>A minha idéia é a seguinte, claramente xy - yx = 0, e portanto para todo o
a
>vale axy - ayx = 0, daí:
>
>fx + gy + axy - ayx = n
>(f + ay)x + (g - ax)y = n, para qualquer a que escolhermos
>
>Quero mostrar que existirá um a, a partir de um dado n, para que f + ay e g
>- ax sejam ambos positivos.
>
>Conseguimos escolher a de modo que (f + ay)x - (g - ax)y = fx - gy + 2ayx
>esteja entre -yx e yx, basta mostrar que nesse intervalo teremos f+ay e
g-ax
>sempre positivos.
>
>Tanto f+ay quanto g-ax podem ficar entre [ n-xy ; n+xy ], ou seja basta que
>n-xy>0 e portanto que n > xy. Logo para N = xy vale o enunciado.
>
>
>Obrigado para quem leu! E tem algum erro?
>Valeu...
>________________________________________________________________________
>Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com
>