Seja
um número primo positivo e sejam
e
com
para
.
(a) Mostre que
, com
inteiro tal que
(b) Mostre que
;
(c) Mostre que
;
(d) Mostre que
.
Sugestão: (Para (a)) Escreva
(a) Mostre que
(b) Mostre que
(c) Mostre que
(d) Mostre que
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
O primeiro produto é
logo
Como para cada j temos jp+k≡k mod p, segue
Isso completa (a).
Passo 3
Para (b), use
e aplique o resultado de (a) em cada fatorial:
O fator pm/(pn p^{m-n})=1, e fica
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
Passo 4
Para (c), separamos m=pm’+m₀ e n=pn’+n₀ com 0≤m₀,n₀<p. Então
Fatorando como em (a) e simplificando dá
Mas cada termo jp+k≡k mod p, logo o quociente é
Assim
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
Resposta
(a)
, com
inteiro e e
, tem-se .)