[obm-l] Olimpiada Polonesa 1983

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Olimpiada Polonesa 1983

> Bem, o Ricardo resolveu o problema 5 da Olimpiada da India de 1995 (eu nao conferi a solucao pois eh uma inducao meio longa, mas se ele garante que tah certo, pra mim tah bom) e com isso, fechou aquela prova.
>
> Mais que depressa, o Dirichlet atacou de Polonia - 1983. Entao, vamos lah!
>
>
> B3.  Show that if the positive integers a, b, c, d satisfy ab = cd, then we have gcd(a,c) gcd(a,d) = a gcd(a,b,c,d). 
>
> Seja  m = mdc(a,c). 
> Entao a = a1*m, c = c1*m, com mdc(a1,c1) = 1.
>
> ab = cd ==> 
> a1*m*b = c1*m*d ==> 
> a1*b = c1*d ==>
> a1 | d   e   c1 | b ==>
> b/c1 = d/a1 = k  (k inteiro positivo) ==>
> b = c1*k  e  d = a1*k
>
> Entao, ficaremos com:
> mdc(a,c)*mdc(a,d) = 
> m*mdc(a1*m,a1*k) = 
> m*a1*mdc(m,k) = 
> a*mdc(m,k)
>
> Alem disso:
> a*mdc(a,b,c,d) = 
> a*mdc(a1*m,c1*k,c1*m,a1*k) = 
> a*mdc( mdc(a1*m,c1*m) , mdc(a1*k,c1*k) ) =
> a*mdc( m*mdc(a1,c1) , k*mdc(a1,c1) ) =
> a*mdc(m*1,k*1) =
> a*mdc(m,k) =
> mdc(a,c)*mdc(a,d)  e acabou...
>
>
> []s,
> Claudio.