Encontre o resto da divisão de
53 ! por 61

Passo 1

Resumindo o enunciado: queremos o resto da divisão de 53! por 61. O conteúdo envolvido é Teorema de Wilson e aritmética modular.

Passo 2

Pelo Teorema de Wilson com p=61 temos
60!equiv -1pmod61 .
Podemos escrever
60!equiv 53!times prodk=54^60kpmod61 .

Passo 3

Definimos
P = prodk=54^60kpmod61 .
Como para k=54,55,56,57,58,59,60 vale kequiv k-61pmod61, temos
54equiv -7,;55equiv -6,;56equiv -5,;57equiv -4,;58equiv -3,;59equiv -2,;60equiv -1 .
Logo
Pequiv (-7)(-6)(-5)(-4)(-3)(-2)(-1) =(-1)^7cdot7! = -7!pmod61 .

Passo 4

Calculamos
7! = 5040
e reduzimos módulo 61. Como 5040 = 61cdot82 + 38, segue
7!equiv 38pmod61
e
Pequiv -38equiv 23pmod61 .

Passo 5

Voltando a 60!equiv 53!times Pequiv -1pmod61, obtemos
53!times 23 equiv -1pmod61
ou seja
53!equiv -1cdot 23^-1pmod61 .

Passo 6

Calculamos o inverso de 23 módulo 61 pelo algoritmo de Euclides e achamos
23^-1equiv 8pmod61
pois 23cdot8=184equiv1pmod61.

Passo 7

Portanto
53!equiv -1cdot8=-8equiv 53pmod61 .

Resposta

O resto da divisão de 53! por 61 é 53.

Exercícios relacionados