Seja p um número primo positivo e sejam
m=m0+m1 p+cdots+ms p^s
e
n=n0+n1 p+cdots+ns p^s
com mi ni in Z^+para i=0, ldots s.
(a) Mostre que (pm)!=p^m cdot m!M, com M inteiro tal que M equiv [(p-1)!]^m bmod p ;
(b) Mostre que binomp mp n equivbinommn bmod p;
(c) Mostre que binommn equivbinomn-m0n-n0binomm0n0 bmod p;
(d) Mostre que binommn equivbinomm0n0 cdotsbinommsns bmod p.
Sugestão: (Para (a)) Escreva
rl (p m)!=p & 2 p cdots m p[1 cdot 2 cdots(p-1)][(p+1) cdots(p+p-1)] cdots & cdots[((m-1) p+1) cdots((m-1) p+p-1)]

Passo 1

O enunciado trata da prova do Teorema de Lucas e resultados auxiliares sobre fatorial e binomial módulo primo. Temos um primo p e escrevemos m e n em base p: m= m₀+ m₁p+⋯+ mₛpˢ e n= n₀+ n₁p+⋯+ nₛpˢ. Vamos precisar das propriedades de fatores de p em factorial e do cancelamento módulo p para concluir as congruências pedidas.

Passo 2

Para (a), escrevemos
(pm)! = prodj=1^pm j = l(prodj=1^m(jp)r) ;l(prodj=0^m-1prodk=1^p-1(jp+k)r)
O primeiro produto é
prodj=1^m(jp)=p^m,m!;
logo
(pm)! = p^m,m!;M, M=prodj=0^m-1prodk=1^p-1(jp+k)
Como para cada j temos jp+k≡k mod p, segue
Mequivprodj=0^m-1prodk=1^p-1k=[(p-1)!]^mpmod p
Isso completa (a).

Passo 3

Para (b), use
binompmpn = (pm)!(pn)!,(p(m-n))!
e aplique o resultado de (a) em cada fatorial:
(pm)! = p^m m! M1,;(pn)! = p^n n! M2,;(p(m-n))! = p^m-n(m-n)! M3
O fator pm/(pn p^{m-n})=1, e fica
binompmpn=binommn;M1M2M3
Como M_1≡[(p-1)!]^m, M_2≡[(p-1)!]^n, M_3≡[(p-1)!]^{m-n} mod p, temos M_1/(M_2M_3)≡1. Portanto
binompmpnequivbinommnpmod p

Passo 4

Para (c), separamos m=pm’+m₀ e n=pn’+n₀ com 0≤m₀,n₀<p. Então
binommn=(pm'+m₀)!(pn'+n₀)!,l(p(m'-n')+(m₀-n₀)r)!
Fatorando como em (a) e simplificando dá
binommnequivbinomm'n';prodk=1^m₀(pm'+k)prodk=1^n₀(pn'+k),prodk=1^m₀-n₀(p(m'-n')+k)pmod p
Mas cada termo jp+k≡k mod p, logo o quociente é
m₀!n₀!,(m₀-n₀)!=binomm₀n₀
Assim
binommnequivbinomm'n'binomm₀n₀pmod p,
que é a redução de um dígito.

Passo 5

Para (d), iteramos o passo de (c) sobre todos os dígitos. Usando indução em s, concluímos
binommnequivbinomm₀n₀binomm₁n₁cdotsbinommₛnₛpmod p

Resposta

(a) , com inteiro e e , tem-se .)

Exercícios de Livros Relacionados