RES: Problema de inteiros

["Marcos Paulo" <mparaujo@xxxxxxxxxxxxx>]

Tem um teorema (acho q eh do Euclides O Zé Paulo me corrija, pois foi meu
professor de Os Números equivalente a álgebra 1)que diz que o m.d.c. entre
dois números sempre pode ser escrito como uma combinação linear entre esses
números.
No seu problema temos m.d.c(a, b)= 1 => xa + yb = 1. (eh fácil chegar aos
possiveis valores de x e y pelo algoritmo de Euclides)daí basta multiplicar
toda a expressão pelo valor de n desejado. Equações do tipo xa + yb = n são
chamadas Equações Diofantinas, que são usadas pra resolver, por exemplo o
problema Chinês do resto (muito interessante por sinal)
Espero ter ajudado.
[]'s M.P.

-----Mensagem original-----
De: owner-obm-l@mat.puc-rio.br [mailto:owner-obm-l@mat.puc-rio.br]Em
nome de Ecass Dodebel
Enviada em: sábado, 22 de abril de 2000 17:42
Para: obm-l@mat.puc-rio.br
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