# Thread: Congruence of factorials when the mod isn't 10 or 15

1. ## Congruence of factorials when the mod isn't 10 or 15

$1!+2!+\dots +1000!\equiv x \ \mbox{(mod 11)}$

When $k\geq 11, k!\equiv 0 \ \mbox{(mod 11)}$

Since we are adding up to 11!, can this be done without $\sum_{i=1}^{10}k!$ individual?

$1!+2!+\dots +10!\equiv x \ \mbox{(mod 11)}$

2. Originally Posted by dwsmith
$1!+2!+\dots +1000!\equiv x \ \mbox{(mod 11)}$

When $k\geq 11, k!\equiv 0 \ \mbox{(mod 11)}$

Since we are adding up to 11!, can this be done without $\sum_{i=1}^{10}k!$ individual?

$1!+2!+\dots +10!\equiv x \ \mbox{(mod 11)}$
Well you can reduce mod 11 each time you multiply. So

1 $\equiv$ 1 mod 11
2 * 1 $\equiv$ 2 mod 11
3 * 2 $\equiv$ 6 mod 11
4 * 6 $\equiv$ 24 $\equiv$ 2 mod 11
5 * 2 $\equiv$ 10 mod 11
6 * 10 $\equiv$ 60 $\equiv$ 5 mod 11
7 * 5 ... etc.

3. Originally Posted by undefined
Well you can reduce mod 11 each time you multiply. So

1 $\equiv$ 1 mod 11
2 * 1 $\equiv$ 2 mod 11
3 * 2 $\equiv$ 6 mod 11
4 * 6 $\equiv$ 24 $\equiv$ 2 mod 11
5 * 2 $\equiv$ 10 mod 11
6 * 10 $\equiv$ 60 $\equiv$ 5 mod 11
7 * 5 ... etc.
So there is no shortcut method of doing this type then? I just have to either add them or do them one at a time and then add the residuals, then.

4. Originally Posted by dwsmith
So there is no shortcut method of doing this type then? I just have to either add them or do them one at a time and then add the residuals, then.
Have a computer do it for you? I don't know of any shortcut or formula beyond what I shared, although one might exist.

PARI/GP is a great CAS for number theory.

Code:
sum(i=1,10,i!%11)%11

5. You might be able to use Wilson's Theorem:

$(n-1)!\equiv -1\pmod{n}$ if and only if $n$ is prime.

In this case, you have $(11-1)!=10!\equiv -1\pmod{11}$. You can use this fact to get $9!$ by multiplying by $10^{-1}$ on both sides. You can get $8!$ by multiplying by $9^{-1}$ after that, and etc...

This method may not really save much time though - you still need to compute modular inverses and peel off terms in the factorial, one by one. Is it really so bad to compute the factorials by hand?