Cómo calcular eficazmente el resto de un factorial principal dividido por un número primo (donde Wilson ' s Teorema es insuficiente)

Question

Este va a ser mi primera pregunta en la sección de Matemáticas, he tropezado aquí mucho, así que aquí estoy ante ustedes hoy para hacer una pregunta a mí mismo...

Hay una pregunta que he sido incapaz de resolver durante años. Es a partir de algunas concurso nacional celebrado en Turquía.

La pregunta es la siguiente:

(20!*12!) mod 2012 is equivalent to which of the following?
A) 344
B) 1062
C) 736
D) 162
E) None of the Above

La respuesta es:

E

Tenga en cuenta que:

Una respuesta válida sería 1684

Ahora, por supuesto, podría conectar este en una calculadora y encontrar la respuesta... Pero, ¿cómo eran los pobres los niños que tomaron esta prueba se pretende resolver?

A través de varias reducciones yo era, y varias otras personas, me he preguntado fueron, capaz de reducir el problema a la siguiente:

4*[ 60 * 11! * 19! mod 503 ]

Ahora que todavía se ve terriblemente feo, lo que realmente he estado buscando es una manera fácil de calcular 11! mod 503 y 19! mod 503. Es allí cualquier teorema o la dicha que me permitirá calcular fácilmente the Remainder of a Prime Factorial Divided by a Prime Number. (Y sí, te puedo asegurar que el 11, 19 y 503 son todos números primos.) Cualquier ayuda sería muy apreciada, gracias a todos de antemano...

Answer 1

Aquí es un (potencialmente) método más rápido:

Los números primos menores de $20$$2, 3, 5, 7, 11, 13, 17, 19$, y la de los números primos en$12$$2, 3, 5, 7, 11$.

El mayor poder de un primer $p$ que divide $n!$ $\left\lfloor\frac{n}{p}\right\rfloor + \left\lfloor\frac{n}{p^2}\right\rfloor + \left\lfloor\frac{n}{p^3}\right\rfloor + ...$

Este enfoque sólo se tarda un par de segundos para que el pequeño de los números primos y muy rápidamente converge a los poderes de $1$, que sabe que va a repetir para el resto de los números primos. Vemos el siguiente:

$$20! \bmod{503} \equiv 2^{18} \cdot 3^{8} \cdot 5^4 \cdot 7^2 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \bmod{503}$$

$$12! \bmod{503} \equiv 2^{10} \cdot 3^5 \cdot 5^2 \cdot 7 \cdot 11 \bmod{503}$$

La multiplicación de estos dos, obtenemos:

$$12! \cdot 20! \equiv 2^{28} \cdot 3^{13} \cdot 5^6 \cdot 7^3 \cdot 11^2 \cdot 13 \cdot 17 \cdot 19 \bmod{503}$$

Y desde aquí se puede reagrupar a los poderes, a simplificar, reducir, etc. Alternativamente, calcular los $12! \bmod {503}$ por sí mismo primero y luego se multiplica por $2^8 \cdot 3^3 \cdot 5^2\cdot 7 \cdot 13 \cdot 17 \cdot 19 \bmod{503}$, que llevaría a $20! \bmod{503}$ (si desea lidiar con el menor de los exponentes).

Creo que la mayoría de la gente requeriría más de $3$ minutos para resolver este tipo de problema. Pero me imagino que hay otros problemas que podrían tomar menos de $3$, por lo que puede compensar.