Correctness of Factorial $(\text{mod } p)$ procedure

Question

While checking out a procedure for finding the factorial of an extremely large number mod a very large prime, I found the following implementation:

int factorial = 1;
for(int i = 1;i <= n;i++)
     factorial = (factorial * i) % m

I've been trying to understand why this is correct, but I can't seem to find an answer.

From what I gather, $a \cdot b \text{ (mod } p) = (a \text{ (mod } p) \cdot b \text{ (mod } p)) \text{ (mod } p) $, but this implementation gives quite a different form for the factorial mod a prime.

Can anyone explain why this is correct ? Or more than that, can you help me understand how would you compute a factorial mod a prime?

Answer 1

Seriously, you ought to that if $a \equiv b \mod M$ then $an \equiv bn \mod M$. This this nothing more than that.

$a \equiv b \mod M \implies$

$a = kM + b \implies$

$an = knM + nb \implies$

$an \equiv nb \mod M$.

So .....

Induction:

let $k = aP + r; r \equiv k \mod P $ for some $a$ and some $k$.

let $(k-1)! \equiv s \mod P $ so $(k-1)! = bP + s $ for some $b$ and some $s$. (This has nothing to do with $(k-1)!$ being a factorial; $(k-1)!$ is an integer and all integers are equal to $mP + n$ for some $m$ and $n$.)

Then $k! = (aP +r)(bP + s)$

$=abP^2 + (br+as)P + rs \equiv rs \mod P $.

And that's it.

~~~~~

Note though if $P < n $ then $n! \mod P =0$. And if all of $P $'s prime factors are larger than $n $ then $n! \mod P = n! $.

~~~~

Small sample: $8! \mod 25$

$4! = 24$

$5! = 120 = 4*25 + 20 \equiv 20 \mod 25$

$6! = (4*25 + 20)6 = 4*6*25 + 6*20 \equiv 6*20 \mod 25 = 6*(5!\%25)\mod 25$

$= 120 \mod 25 \equiv 20 \mod 25$

so $6! = 4*6*25 + 4*25 + 20= 28*25 + 20$

$7! = (28*25 + 20)7 = 7*28*25 + 20*7 \equiv 20*7 \mod 25 = 140 \equiv 15 \mod 25 $

So $7! = M*25 + 15$ where $M = 7*28 + 4$ whatever the hell that is.

So $8! = (M*25 + 15)*8 \equiv 8*15 \mod 25 = 8*(7! \% 25) = 120 \mod 25 \equiv 20 \mod 25$.

~~~

Smaller example $5! = 120 \equiv 3 \mod 9$

$3! = 6$

$4! = 24 = 2*9 + 6;$ so $6 = (4! \% 9)$

$5! = (2*9 + (4! \% 9))5 = 5*2*9 + 5*(4! \% 9) \equiv 5*(4! \% 9) \mod 9$.

or simpler:

$1! =1$

$2! = 2$

$3! = 6$

$4! = 24 \equiv 6 \mod9$

$5! \equiv 6*5 = 30 \equiv 3 \mod 9$.

~~~