Encontre o resto da divisão de
65 ! por 71

Passo 1

O enunciado pede o resto da divisão de 65! por 71. Como 71 é primo, vamos usar o Teorema de Wilson para reduzir o fatorial.

Passo 2

O Teorema de Wilson diz que, se p é primo, então
(p-1)! equiv -1 pmod p
Como p=71, temos
70! equiv -1 pmod71

Passo 3

Podemos escrever
70! = 65! times 66 times 67 times 68 times 69 times 70
Logo,
65! times (66cdot67cdot68cdot69cdot70) equiv -1 pmod71,
e daí
65! equiv -l(66cdot67cdot68cdot69cdot70r)^-1 pmod71

Passo 4

Cada fator modulo 71 é
66equiv -5, 67equiv -4, 68equiv -3, 69equiv -2, 70equiv -1pmod71
Então o produto é
(-5)(-4)(-3)(-2)(-1) = -120 equiv 22 pmod71
Chamando Pequiv22, temos
65! equiv -P^-1 pmod71

Passo 5

Para achar P^-1 com P=22, usamos o algoritmo de Euclides estendido:
71 = 3cdot22 + 5,
22 = 4cdot5 + 2,
5 = 2cdot2 + 1.
Retrocedendo,
1 = 5 - 2cdot2 = 5 - 2,(22 - 4cdot5) = 9cdot5 - 2cdot22 = 9,(71 - 3cdot22) - 2cdot22 = 9cdot71 -29cdot22
Logo -29cdot22equiv1pmod71, isto é,
22^-1 equiv -29 equiv 42 pmod71

Passo 6

Substituindo em 65! equiv -P^-1, obtemos
65! equiv -42 equiv 29 pmod71

Resposta

O resto da divisão de 65! por 71 é 29.

Exercícios relacionados