# 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?

• Also $a \cdot b\; (mod\; p) = (a\; (mod\; p) \cdot b)\; (mod\; p)$ which is essentially what the code does. What specifically bugs you about it? – dxiv Aug 19 '16 at 23:31
• There it is, the way you wrote it.. Why is there no mod p applied on $b$ ? – johnnmath Aug 19 '16 at 23:37
• That's an implementation detail, maybe for saving a $(mod\;p)$ operation at the price of possibly overflowing earlier. Anyway, the result is mathematically the same whether you apply $(mod\;p)$ to either or both operands before applying it at the end to the result of the multiplication. If that's not obvious, write $a = p q_a + r_a, b = p q_b + r_b$ where $r_a = a\;(mod\;p), r_b = b\;(mod\;p)$ and verify the result in each case by hand. – dxiv Aug 19 '16 at 23:45
• It is like calculating the factorial in $GF(p,1)$. Whether you do the modulo operation after each multiplication or whether you do the modulo operation once for the whole product, is equal. Note that a computer can multiplicate smaller numbers quicker than larger ones. If your computer works with $p$-adic numbers, then the modulo operation can be done very quickly. – S. M. Roch Aug 20 '16 at 0:06
• Um... if $p > n$ then $n! \equiv n! \mod p$. If $p \le n$ then $n! \equiv 0 \mod p$. – fleablood Aug 20 '16 at 1:28

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

~~~