Problema numero 3 - The theory of numbers

Determinar el residuo no negativo de

1! + 2! + 3! +....+ 500! módulo 189

Cuando lo vi al principio dije imposible y lo dejé arrinconado peo ahora que lo he pensado le he encontrado el "truco"

Si un número es múltiplo del módulo el residuo es cero, lógico ya que el residuo es el resto de dividir por el módulo.

Entonces todos los múltiplos de 189 tendrán residuo 0 y no hay que calcularlos.

Eso en principio me hizo pensar que había que calcular hasta el 189! Que seguí siendo imposible en la práctica, pero luego pensé más

Descomponiendo 189 en factores primos tenemos

189 | 3
 63 | 3
 21 | 3
  7 | 7

Un factorial tiene todos los factores de los números anteriores

Luego 3! Y siguientes tienen 1 factor primo 3

6! Y siguientes tendrán 2 factores primos 3

9! Y siguientes ya tienen 4 factores primos 3

Además 7! Y siguientes tienen 1 factor primo 7

Cuando haya más de 3 factores primos 3 y 1 factor primo 7 el factorial ya es múltiplo de 189 y los siguientes con mayor motivo.

Con 9! Se inauguran los múltiplos de 189 luego solo debemos calcular los residuos de los factoriales hasta 8

1! :~ 1 (mod 189)

2! :~ 2 (mod 189)

3! :~ 6 (mod 189)

4! :~ 24 (mod 189)

5! :~ 120 (mod 189)

6! = 720 :~ 720 - 3·189 :~ 153 (mod 189)

7! :~ 7·153 :~ 1071 :~ 1071 - 5·189 :~ 126 (mod 189)

8! :~ 8·126 :~ 1008 :~1008 - 5·189 :~ 63 (mod 189)

Y ahora las sumamos

1! + 2! + ...+ 8! :~ 1+2+6+24+120+153+126+63 :~ 495 :~ 495 - 2·189 :~ 117 (mod 189)

Luego la respuesta es 117

Puede ser discutible si esta es la forma más corta o haber sumado los 8 factoriales y hacer una sola vez la reducción al congruente mínimo

1+2+6+24+120+720+ 7! + 8! = 46233

46233 / 189 =244.619...

46233 - 244·189 = 117

Esta vez sirve, pero otras veces estas cuentas no caben en la calculadora.

Y eso es todo.