[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: [obm-l] Caso de divisibilidade
Um jeito mais fácil é usar a velha e, espero, conhecida fórmula para o expoente de p em n!, igual a [n/p] + [n/p^2] + [n/p^3] + ....
O expoente de p no numerador de Binom(p^m,k) (1 <= k <= p^m - 1) é:
[p^m/p] + [p^m/p^2] + ... + [p^m/p^(m-1)] + [p^m/p^m] =
p^(m-1) + p^(m-2) + ... + p + 1.
O expoente de p no denominador de Binom(p^m,k) é a soma de:
[k/p] + [k/p^2] + [k/p^3] + ....
e
[(p^m-k)/p] + [(p^m-k)/p^2] + [(p^m-k)/p^3] + ...
Mas:
[k/p^j] + [(p^m - k)/p^j] <= [(k + (p^m-k))/p^j] = [p^m/p^j] = p^(m-j).
Além disso, para k = 1, teremos:
[1/p^j] + [(p^m - 1)/p^j] = p^(m-j) - 1 < p^(m-j) = [p^m/p^j]
A partir dessas duas desigualdades é fácil concluir que o expoente de p no numerador é estritamente maior do que o expoente de p no denominador, de modo que p divide Binom(p^m,k).
[]s,
Claudio.
| De: |
owner-obm-l@mat.puc-rio.br |
| Para: |
obm-l@mat.puc-rio.br |
| Data: |
Fri, 17 Jun 2005 17:48:08 -0300 |
| Assunto: |
RE: [obm-l] Caso de divisibilidade |
> Oi, Maurício,
> é possível resolver essa como aplicação imediata do teorema de lucas, que
> é o seguinte:
>
> Se m = a_k*p^k + a_(k-1)*p^(k-1) + ... + a_1*p + a_0 e n = b_k*p^k + ...
> + b_0 (representação na base p), denotando B(m,n) a combinação de m elementos
> tomados n a n, vale
>
> B(m,n) == B(a_0,b_0)*B(a_1,b_1)*...*B(a_k,b_k)(mod p),
>
> onde B(x,y) = 0 se y > x.
>
> Mas eu ainda gostaria de ver uma prova mais elementar deste fato...
>
> []s,
> Daniel
>
> '>' Oi, pessoal,
> '>'
> '>' Estou em cima desse exercício de teoria dos números
> '>'faz tempo e não cheguei a nada, alguém tem alguma
> '>'dica?
> '>'
> '>' Mostrar que o número de combinações de p^a (p
> '>'elevado a a) elementos tomados k a k é divisivel por
> '>'p, supondo p^a>k (acho que também é necessário que
> '>'a>1). Formulei isso assim:
> '>'
> '>' p^a!/(k!(p^a-k)!) = 0 (mod p)
> '>'
> '>'
> '>' Abraços,
> '>' Maurício
> '>'
> '>'
> '>'
> '>'
> '>'
> '>'____________________________________________________
> '>'Yahoo! Sports
> '>'Rekindle the Rivalries. Sign up for Fantasy Football
> '>'http://football.fantasysports.yahoo.com
> '>'=========================================================================
> '>'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
> '>'=========================================================================
>
>
>
> =========================================================================
> 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
> =========================================================================
>