Resto da divisão - Fatorial

Ir em baixo

Resto da divisão - Fatorial

Mensagem por Luís Eduardo em Seg Ago 15, 2011 9:44 pm

Qual é o resto da divisão de 63! por 71.
avatar
Luís Eduardo
Admin
Admin

Mensagens : 288
Data de inscrição : 09/08/2011

Ver perfil do usuário http://momentum21.forumeiros.com

Voltar ao Topo Ir em baixo

Re: Resto da divisão - Fatorial

Mensagem por Luís Eduardo em Seg Ago 15, 2011 9:44 pm

Para resolver esse tipo de questão é importante conhecer o Teorema de Wilson:

(p - 1)! ≡ - 1 (mod 71)

70! ≡ - 1 (mod 71)


Sabemos que:


70! = 70.69.68.67.66.65.64.63!


70.69.68.67.66.65.64.63! ≡ - 1 (mod 71)

Sabemos pelas propriedades de congruência que:

a≡c (mod m)

d≡e (mod m)

Logo, a.d ≡ c.e (mod m) ---> Procure a demonstração na internet.


Então, devemos fazer:

63! ≡ x (mod 71)

70.69.68.67.66.65.64 ≡ w (mod 71)

Vamos por partes:

70.64 = 4480 ≡ 7 (mod 71)
69.65 = 4485 ≡ 12 (mod 71)
68.64 = 4488 ≡ 15 (mod 71)
67 ≡ -4 (mod 71)

Multiplicando tudo achamos que:

70.69.68.67.66.65.64 ≡ -5040 (mod 71)

Agora,

-5040 ≡ 1 (mod 71)

Logo, w = 1.


Pelo Teorema de Wilson, x.w = - 1
Logo, x.1 = - 1
x = - 1


Entretanto, queremos um resto positivo, então, é só fazer:

-1 ≡ 70 (mod 71)

Assim, podemos concluir que o resto será 70.


hehehe Very Happy Very Happy
avatar
Luís Eduardo
Admin
Admin

Mensagens : 288
Data de inscrição : 09/08/2011

Ver perfil do usuário http://momentum21.forumeiros.com

Voltar ao Topo Ir em baixo

Voltar ao Topo

- Tópicos similares

 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum