5
$\begingroup$

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...

$\endgroup$
8
  • $\begingroup$ Given your "note", I don't get how the answer is not E. $\endgroup$ – The Count May 1 '17 at 14:33
  • $\begingroup$ Did you read the second spoiler :P and the "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?" part? $\endgroup$ – madprogramer May 1 '17 at 14:33
  • $\begingroup$ Oh, wow, I didn't even see the first one. Wacky! Sorry. haha. $\endgroup$ – The Count May 1 '17 at 14:34
  • $\begingroup$ Are people required to calculate this under 1 minute? Else if you give me 5 minutes, I can calculate the given thing mechanically using basic congruences. You don't kneed to calculate 11!*19! yo calculate the remainder mod 503. Once you have that, use Chinese Remainder Theorem. $\endgroup$ – IamThat May 1 '17 at 14:47
  • 3
    $\begingroup$ We can rule out B and D immediately because they are not multiples of $4$. $\endgroup$ – Ross Millikan May 1 '17 at 16:27
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.