How to efficiently calculate the remainder of a prime factorial divided by a prime number (where Wilson's Theorem is insufficient)

Question

This'll be my first question in the Mathematics section, I've stumbled upon here quite a lot, so here I stand before you today to ask a question myself...

There's this question which I've been unable to solve for years. It's from some nationwide competition held in Turkey.

The question asks the following:

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

The answer is:

E

Do note that:

A valid answer would be 1684

Now sure, I could just plug this into a calculator and find the answer... But how were the poor kids who took this exam meant to solve it?

Through several reductions I myself was, and several other people I've asked the question were, able to reduce the problem to the following:

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

Now that still looks terribly ugly, what I've really been searching for is an easy way to calculate 11! mod 503 and 19! mod 503. Is there any theorem or the such which will allow me to easily calculate the Remainder of a Prime Factorial Divided by a Prime Number. (And yes, I can assure you that 11, 19 and 503 are all prime numbers.) Any help would be much appreciated, thank you all in advance...

Answer 1

Here is a (potentially) faster method:

The primes under $20$ are $2, 3, 5, 7, 11, 13, 17, 19$, and the primes under $12$ are $2, 3, 5, 7, 11$.

The largest power of a prime $p$ that divides $n!$ is $\left\lfloor\frac{n}{p}\right\rfloor + \left\lfloor\frac{n}{p^2}\right\rfloor + \left\lfloor\frac{n}{p^3}\right\rfloor + ...$

This approach only takes a couple seconds for the small primes and very quickly converges to powers of $1$, which you know will repeat for the rest of the primes. We see the following:

$$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}$$

Multiplying these two, we get:

$$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}$$

And from here you can regroup powers, simplify, reduce, etc. Alternatively, compute $12! \bmod {503}$ by itself first and then multiply it by $2^8 \cdot 3^3 \cdot 5^2\cdot 7 \cdot 13 \cdot 17 \cdot 19 \bmod{503}$, which would carry it to $20! \bmod{503}$ (if you wish to deal with smaller exponents).

I think most people would require more than $3$ minutes to solve this kind of problem. But I imagine there are other problems that would take fewer than $3$, so it may balance out.