Correctness of Factorial $(\text{mod } p)$ procedure 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?
 A: 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$.
~~~
