RE: [obm-l] Caso de divisibilidade

["Maurício" <briqueabraque@xxxxxxxxx>]

  Cláudio, Daniel, outros,

  Consegui encontrar vários contra-exemplos para esse
problema. Sendo comb(a,b) o número de combinações de a
elementos tomados b a b, ou comb(a,b)=a!/((a-b)!b!),
pede-se mostrar que comb(a^c,b)=0(mod a), para c>=2,
a^c>b. Entretanto:

comb(6^2,4) = 3 (mod 6)
comb(22^2,4) = 11 (mod 22)
comb(6^3,8) = 3 (mod 6)
comb(6^2,9) = 4 (mod 6)
comb(12^2,9) = 4 (mod 12)
comb(10^2,25) = 4 (mod 10)
comb(6^3,27) = 2 (mod 6)
comb(33^2,121) = 9 (mod 33)
comb(21^3,343) = 6 (mod 21)

  Pode ser que eu tenha errado alguma coisa na hora de
programar o computador para fazer as contas, mas pelo
menos o primeiro exemplo eu conferi na mão. Eu não
achei esses números ao acaso. Em todos eles, sendo a =
p*q, com p e q primos, eu fiz b = p^c e escolhi um q
que desse problema.

  Abraços,
  Maurício


>   Interessante! Dei uma olhada no livro que estou
estudando e ele menciona essa fórmula (...)

> > 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)] +
> > (...)
> > 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.

> > > Oi, Maurício,
> > > é possível resolver essa como aplicação imediata
do teorema de lucas, que é o seguinte:
> > > (...)
> > > 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?
> > > > (...)
 

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.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
=========================================================================