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

Printable View

June 26th 2010, 08:55 PM
dwsmith

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)}$
June 26th 2010, 09:08 PM
undefined

Quote:

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.
June 26th 2010, 09:10 PM
dwsmith

Quote:

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.
June 26th 2010, 09:16 PM
undefined

Quote:

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
June 26th 2010, 09:48 PM
roninpro

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?