Re: [obm-l] russos

["marcelo oliveira" <marcelo_rufino@xxxxxxxxxxx>]

Para a segunda questão faça o seguinte:

>2)Dados quaisquer numeros naturais  "m" ,"n" e "k' . prove que  nós
>sempre  podemos  encontrar dois numeros "r" e "s", primos entre si , tal 
>que r*m + s*n é um multiplo de k.

Dividamos inicialmente m e n por k:  m = x.k + r1   e   n = y.k + r2, onde  
r1 <= 0.
Notemos que sempre é possível fazer isto, bastando fazer a divisão 
euclidiana tradicional, com o resto r3 entre 0 e k - 1  (m = z.k + r3), e 
depois:  m = z.k + r3 = (z + 1).k + (r3 - k) = x.k + r1
ou seja,  x = z + 1  e  r1 = r3 - k

Assim:
r.m + s.n = r.x.k + r.r1 + s.y.k + s.r2 = k(r.x + s.y) + r.r1 + s.r2
Seja  d = mdc (r1, r2)   =>   mdc (r1/d, r2/d) = 1
Fazendo  r = r2/d  e  s = – r1/d, temos que  r.r1 + s.r2 = 0   =>
p | am + bn

Repare que o cuidado em fazer r1 <= 0 é no sentido de forçar que s >= 0.


Por exemplo, suponha que  m = 10   n = 34  k = 7
m = 2.7 - 4
n = 4.7 + 6
mdc (- 4, 6) = 2
Assim:  s = 4/2 = 2   e   r = 6/2 = 3
Testando:  r.m + s.n = 3(10) + 2(34) = 30 + 64 = 84 = 7.12


Até mais,
Marcelo Rufino




_________________________________________________________________
MSN Photos is the easiest way to share and print your photos: 
http://photos.msn.com/support/worldwide.aspx

=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================