Resto da divisão

por Diogo Qui 14 Jul 2011, 16:22

Qual é o resto da divisão de 63! por 71.

por **Euclides** Sáb 16 Jul 2011, 21:02

Prá mim tá difícil!

up

por **luiseduardo** Dom 17 Jul 2011, 00:31

Realmente Euclides, a questão não é fácil, mas estava preso numa besteira. Agora já sei como resolver:

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